1.题目基本信息

1.1.题目描述

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。

实现 Solution class:

• Solution(int[] nums) 使用整数数组 nums 初始化对象

• int[] reset() 重设数组到它的初始状态并返回

• int[] shuffle() 返回数组随机打乱后的结果

1.2.题目地址

https://leetcode.cn/problems/shuffle-an-array/description/

2.解题方法

2.1.解题思路

Fisher-Yates洗牌算法

3.解题代码

python代码

class Solution:
    # Fisher-Yates洗牌算法
    def __init__(self, nums: List[int]):
        self.oriArr = nums.copy()
        self.nums = nums

    def reset(self) -> List[int]:
        self.nums = self.oriArr.copy()
        return self.nums

    def shuffle(self) -> List[int]:
        # 依次枚举，和后面的元素进行随机置换
        for i in range(len(self.nums)):
            index = random.randrange(i, len(self.nums))
            self.nums[i], self.nums[index] = self.nums[index], self.nums[i]
        return self.nums

c++代码

class Solution {
private: 
    vector<int> nums;
    vector<int> original;
public:
    Solution(vector<int>& nums) {
        this->nums = nums;
        this->original.resize(nums.size());
        copy(nums.begin(), nums.end(), original.begin());
    }
    
    vector<int> reset() {
        copy(original.begin(), original.end(), nums.begin());
        return nums;
    }
    
    vector<int> shuffle() {
        for (int i = 0; i < nums.size(); i++) {
            int index = rand() % nums.size();
            int temp = nums[i];
            nums[i] = nums[index];
            nums[index] = temp;
        }
        return nums;
    }
};

4.执行结果