洗牌算法

洗牌算法

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。

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

打乱的概念

• 随机打乱后的结果能够覆盖所有的情况，比如数组元素的个数为n，那么打乱后的结果应该覆盖$n!$种所有可能的结果

• 所有结果等概率出现

方法一 暴力

暴力的方法就是模拟，假设数组中的每个元素为一个小球，我们将其放入袋子中，进行不放回的抽取，直到袋子中没有小球，我们将抽取出来的小球按顺序排列得到一个排列组合，这个排列组合出现的概率为$\frac{1}{n!}$，因此这个 数组的每个排列组合都是等概的，算法时间复杂度$O(n2)$，vector<int>的erase()删除操作是O(n)的。

对于某一个排列组合其出现概率为
$$
\mathop{\Pi}\limits_{k = 0}^{n - 1}\frac{1}{n - k} = \frac{1}{n!}
$$

方法二 Fisher-Yates算法

Fisher-Yates 洗牌算法跟暴力算法很像。在每次迭代中，生成一个当前数组末尾指针下标的随机整数。接下来，将当前元素和随机选出的下标所指的元素互相交换，这步模拟了每次从袋子里面摸一个元素的过程。

vector<int> shuffle(vector<int>& arr) {
    int n = arr.size();
    for (int i = n - 1; i >= 0; --i) {
        int pos = rand() % (i + 1);
        swap(arr[i], arr[pos]);
    }
    return arr;
}