384.打乱一个没有重复元素的数组 (Medium)*
题目描述*
思路 & 代码*
不懂为啥 leetcode 会出这题，测试用例是怎么写。。。而且我第一次提交竟然还 wa 了 ？？？
打乱算法的主要问题就是怎么保证算法是真的乱。其实就是利用随机性来实现，主要的框架如下：
int randInt(int min, int max);
void shuffle(vector<int>& nums) {
int n = nums.size();
for(int i = 0; i < n; i++) {
int rand = randInt(i, n - 1);
swap(nums[i], nums[rand]);
}
}
数组的打乱就是生成随机的下标然后交换，要注意的是随机下标的范围，应该保证最后的可能结果有 n! 个，如果所有下标都是从 [0, n - 1] 生成，那么最终的可能结果应该是 n^n 种，而且 n^n \not \equiv 0 \mod n!，所以不可能保证每种情况概率相同。
最后更新: July 23, 2022