384. Shuffle an Array.md

384. Shuffle an Array

思路

给定一个没有重复元素数组，将其随机打乱，即洗牌。

思路一、暴力（Fisher–Yates Shuffle）

先看最暴力的解法，想象一下我们先将所有牌放到一个黑箱里面，然后不断从中不放回地随机抽取一张，这样最后得到的就是洗好的牌。

实现上我们可以用一个循环，第一循环时从整个数组中随机选一个元素然后将这个元素从数组中删掉；第二次循环再从中选出一个元素.....。

因为一共进行了n次循环，每次将数组中的元素删除是线性复杂度的，所以时间复杂度O(n^2)，空间复杂度O(n)。

思路二、Knuth-Durstenfeld Shuffle

思路一每次循环的删除操作是线性复杂度的，可以优化至常数复杂度：我们每次将要删除的元素和最末尾的元素交换，然后删除末尾元素（其实不用删除，记录一下就是）。

优化后的暴力法就是Knuth-Durstenfeld洗牌算法了：在每次迭代中，生成一个范围在当前下标到数组末尾元素下标之间的随机下标。 接下来，将当前元素和随机选出的下标所指的元素互相交换（这一步模拟了每次从黑箱里面摸一张牌的过程），这样每次被随机选中的元素都不会再被选中（相当于已经删除了）。

注意：当前元素是可以和它本身互相交换的。

可见 Knuth-Durstenfeld是一个in-place算法，原始数据被直接打乱，这也是Python中random.shuffle(list)所采用的方法。

时间复杂度O(n)，空间复杂度为O(1)

思路三、Inside-Out 算法

思路二将原始数据直接打乱，且原数组大小是已知的，所以无法处理暂时不知道长度或动态增长的数组。Inside-Out 算法就是来解决这个问题。

Inside-Out算法的基本思想是：前向后扫描原始数据的拷贝（当前时刻只会用前i个数，所以可以应对数组大小暂时未知，或者说原数组是一个动态增加的情况），设扫描到了位置 i，此时nums_copy[0,...,i-1]已经是打乱的了，而nums_copy[i,i+1,...]还是原始顺序，我们在[0, i]之间随机选择一个下标j，然后交换第i个第j个数:swap(nums_copy[i], nums_copy[j])。

证明：

• 原数组中 i 位置元素在新数组的 k (k <= i) 位置的概率都是：1/(i+1) * [(i+1)/(i+2) * (i+2)/(i+3) ... (n-1)/n] = 1/n（即在第i次刚好随机选择了与k位置交换，且在后面的n-i-1次选择中都不被选中）；
• 原数组中 i 位置元素在新数组的 k (k > i) 位置的概率都是：1/(k+1) * [(k+1)/(k+2)] * [(k+2)/(k+3)]...[(n-1)/n] = 1/n（即在第k次刚好随机选择了与i位置交换，在后面的n-k-1次选择中都不被选中）。

时间复杂度O(n)，空间复杂度O(n)

C++

思路二

class Solution {
private:
    vector<int>nums_origin;
    vector<int>nums_shuffle;
    int size;
public:
    Solution(vector<int>& nums) {
        nums_origin = nums;
        nums_shuffle = nums;
        size = nums.size();
    }
    
    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        return nums_origin;
    }
   
    vector<int> shuffle() {
        // 反向迭代
        for(int i = size - 1; i >= 0; i--)
            swap(nums_shuffle[i], nums_shuffle[rand() % (i + 1)]);
        // 正向迭代
        // for(int i = 0; i < size; i++){
        //     int rand_idx = rand() % (size - i) + i;
        //     swap(nums_shuffle[i], nums_shuffle[rand_idx]);
        // }
        return nums_shuffle;
    }
};

思路三

lass Solution {
private:
    vector<int>nums_origin;
    vector<int>nums_shuffle;
    int size;
public:
    Solution(vector<int>& nums) {
        nums_origin = nums;
        nums_shuffle = nums;
        size = nums.size();
    }
    
    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        return nums_origin;
    }
    
    vector<int> shuffle() {
        for(int i = 0; i < size; i++){
            int j = rand() % (i + 1);
            nums_shuffle[i] = nums_shuffle[j];
            nums_shuffle[j] = nums_origin[i];
        }
        return nums_shuffle;
    }
};