核心思想
洗牌算法（Knuth shuffle算法）：对于有n个元素的数组来说，为了保证洗牌的公平性，应该要能够等概率的洗出n!种结果。
举例解释如下：
开始数组中有五个元素；
在前五个数中随机选一个数与第五个数进行交换，每个数都有五分之一的概率被交换到最后一个位置；
在前四个数中随机选一个数与第四个数进行交换，每个数都有五分之一的概率被交换到第四个位置；
在前三个数中随机选一个数与第三个数进行交换，每个数都有五分之一的概率被交换到第三个位置；
综上所述，每个数都有相等的概率被放到任意一个位置中，即每个位置中出现任意一个数的概率都是相同的。这，就是洗牌算法。
题目
384. 打乱数组
复杂度
时间复杂度为
O
(
n
)
O(n)
O(n)，空间复杂度为
O
(
n
)
O(n)
O(n)
代码
class Solution {
public:
vector<int> a;
Solution(vector<int>& nums) {
a = nums;
}
vector<int> reset() {
return a;
}
vector<int> shuffle() {
auto b = a;
int n = a.size();
for (int i = 0; i < n; i ++) {
swap(b[i], b[i + rand() % (n - i)]);
}
return b;
}
};
/**
* 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();
*/
参考
Knuth 洗牌算法
