目的

设计一个方法, 把一个数组随机打乱, 每一个元素不能在原来的位置上

输入: [1, 2, 3, 4, 5, 6]

输出:

1
2
3
[2, 3, 4, 5, 6, 1]
[6, 4, 2, 3, 1, 5]
[5, 1, 4, 6, 3, 2]

想到的解决方法: 遍历数组(长度为len), 将当前元素(下标i)和它后面([i+1, len])的随机的一个位置交换即可. 但是 Java 的 Random().nextInt(bound) 生成的随机数区间是 [0, bound), 我期望的随机数区间是 [i, bound]. 所以难点在于让生成的随机数位于指定的区间.

经过搜索发现, 生成指定区间的随机数的公式:

1
2
3
4
/**
[0, max) % (max - min + 1) + min => [min, max]
*/
new Random().nextInt(max) % (max - min + 1) + min;

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void random(int[] arr) {
if (arr == null) {
throw new NullPointerException();
}
int len = arr.length;
for (int i = 0; i < len - 1; i++) {
int min = i + 1;
int max = len - 1;
int r = new Random().nextInt(max) % (max - min + 1) + min;
int tem = arr[i];
arr[i] = arr[r];
arr[r] = tem;
}
}

更新

上面说的 Random 区间问题, 在其他地方看到可以从尾到头遍历数组, 这样每次需要的随机数区间就变成 [0, i) 了, 不需要再做上面求 [i, bound] 随机区间的操作. 感觉妙呀 🐱

1
2
3
4
5
6
7
8
9
10
11
12
void random(int[] arr) {
if (arr == null) {
throw new NullPointerException();
}
int len = arr.length;
for (int i = len-1; i > -1; i--) {
int r = new Random().nextInt(i+1); // 生成 [0, i) 区间内的随机数
int tem = arr[i];
arr[i] = arr[r];
arr[r] = tem;
}
}