(随机)384. 打乱数组

384. 打乱数组

Fisher-Yates算法
红色箭头是随机挑到的，蓝色箭头是当前下标，需要蓝色和红色箭头的元素互换，然后蓝色跳到下一个。

题解

class Solution {
public:
    vector<int> arr;

    Solution(vector<int> &nums) {
        arr = nums;
    }

    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        return arr;
    }

    /** Returns a random shuffling of the array. */
    vector<int> shuffle() {
        vector<int> tmp = arr;
        vector<int> res(arr.size());
        for (int i = 0; i < tmp.size(); i++) {
            int sz = tmp.size() - i;
            int idx = rand() % sz;
            swap(tmp[i], tmp[i + idx]);
            res[i] = tmp[i];
        }
        return res;
    }
};