LeetCode384 打乱数组

链接： https://leetcode-cn.com/problems/shuffle-an-array/

题面

给定一个数组，要求实现两个指令函数。第一个函数“shuffle”可以随机打乱这个数组，第二个函数“reset”可以恢复原来的顺序。

解法

学习一手经典的 Fisher-Yates 洗牌算法，原理是通过随机交换位置来实现随机打乱。
算法的伪代码如下：

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

从后向前遍历，每次把当前数字和当前位置前的随机一个数进行交换，即可得到一个随机的数组

代码

class Solution {
    vector<int> origin;
public:
    Solution(vector<int>& nums): origin(move(nums)) {
    }
    
    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        return origin;
    }
    
    /** Returns a random shuffling of the array. */
    vector<int> shuffle() {
        if (origin.empty()) return {};
        vector<int> shuffled(origin);
        int n = origin.size();
        for (int i = n - 1; i >= 0; i--) {
            swap(shuffled[i], shuffled[rand() % (i + 1)]);
            // random 一个小于等于i的下标 并将两者交换
        }
        return shuffled;
    }
};