洗牌-乱序一个数组

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

目的

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

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

输出:

[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;
    }
}