LeetCode 384. Shuffle an Array

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();

解析：

给定一个数组，随机打乱顺序。

首先介绍一个抽样算法：蓄水池抽样算法

问题描述：

给定一个数据流，数据流长度N很大，且N直到处理完所有数据之前都不可知，请问如何在只遍历一遍数据（O(N)）的情况下，能够随机选取出m个不重复的数据。

思路描述：

1.如果接收的数据量小于m，则依次放入蓄水池。
2.当接收到第i个数据时，i >= m，在[0, i]范围内取以随机数d，若d的落在[0, m-1]范围内，则用接收到的第i个数据替换蓄水池中的第d个数据。
3.重复步骤2。

这道题目的处理也是类似于上述算法。挨个位置遍历，每次都随机生成一个坐标位置，然后交换当前遍历位置和随机生成的坐标位置的数字，这样如果数组有n个数字，那么我们也随机交换了n组位置，从而达到了洗牌的目的，一句话描述就是：依次遍历列表中的每一位，并将这一位与其后面的随机一位交换顺序。

代码如下：

class Solution {
public:
    Solution(vector<int>& nums) {
        origin_data = nums;
    }
    
    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        return origin_data;
    }
    
    /** Returns a random shuffling of the array. */
    vector<int> shuffle() {
        vector<int> res = origin_data;
        int len = res.size();
        for(int i=0; i < len; i++)
        {
            int index = i + rand()%(len-i);
            swap(res[i], res[index]);
        }
        return res;
    }
    vector<int> origin_data;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(nums);
 * vector<int> param_1 = obj->reset();
 * vector<int> param_2 = obj->shuffle();
 */