核心思想

洗牌算法（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 洗牌算法