题目
打乱一个没有重复元素的数组。
示例:
// 以数字集合 1, 2 和 3 初始化数组。
int[] nums = {1,2,3};
Solution solution = new Solution(nums);
// 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。
solution.shuffle();
// 重设数组到它的初始状态[1,2,3]。
solution.reset();
// 随机返回数组[1,2,3]打乱后的结果。
solution.shuffle();
难点分析
1、怎么样随机产生下标并且不重复？
一开始可能会考虑这个问题，选择了用map数组记录下标是否已经生成，map[randomIndex]==1表示下标已生成，randomIndex = (randomIndex + 1) % nums.length，可惜这样的算法结果没有通过。
答案分析
借鉴别人的算法，这个算法叫做随机乱置算法或者洗牌算法
需要注意两个问题：
- 什么叫做「真的乱」？
- 设计怎样的算法来打乱数组才能做到「真的乱」？
此类算法都是靠随机选取元素交换来获取随机性。
伪代码：
// 得到一个在闭区间 [min, max] 内的随机整数
int randInt(int min, int max);
// 第一种写法
void shuffle(int[] arr) {
int n = arr.length();
/******** 区别只有这两行 ********/
for (int i = 0 ; i < n; i++) {
// 从 i 到最后随机选一个元素
int rand = randInt(i, n - 1);
/*************************/
swap(arr[i], arr[rand]);
}
}
// 第二种写法
for (int i = 0 ; i < n - 1; i++)
int rand = randInt(i, n - 1);
// 第三种写法
for (int i = n - 1 ; i >= 0; i--)
int rand = randInt(0, i);
// 第四种写法
for (int i = n - 1 ; i > 0; i--)
int rand = randInt(0, i);
作者：labuladong
链接：https://leetcode-cn.com/problems/two-sum/solution/xi-pai-suan-fa-shen-du-xiang-jie-by-labuladong/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
分析洗牌算法正确性的准则：产生的结果必须有 n! 种可能，否则就是错误的。
正确性衡量标准：对于每种可能的结果出现的概率必须相等，也就是说要足够随机。可以利用蒙特卡罗方法：当打的点足够多的时候，点的数量就可以近似代表图形的面积。通过面积公式，由正方形和圆的面积比值是可以很容易推出圆周率的。当然打的点越多，算出的圆周率越准确，充分体现了大力出奇迹的真理。
我的答案：
class Solution {
private int[] nums;
private static Random random = new Random();
public Solution(int[] nums) {
this.nums = nums;
}
/** Resets the array to its original configuration and return it. */
public int[] reset() {
return nums;
}
/** Returns a random shuffling of the array. */
public int[] shuffle() {
int[] rs = Arrays.copyOf(nums, nums.length);
for (int i=0; i<nums.length; i++) {
int index = random.nextInt(nums.length-i) + i;
int tmp = rs[i];
rs[i] = rs[index];
rs[index] = tmp;
}
return rs;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(nums);
* int[] param_1 = obj.reset();
* int[] param_2 = obj.shuffle();
*/
- 执行用时 :280 ms, 在所有 Java 提交中击败了82.90%的用户
- 内存消耗 :81.3 MB, 在所有 Java 提交中击败了60.66%的用户