乐者为王

Do one thing, and do it well.

如何从数组中抽取随机不重复的数字

今天浏览订阅的博客时发现了一个巧妙的从数组中抽取随机不重复数字的算法。譬如,在100个不重复的数字中选择10个不相同的数字,通过这个算法就不需要修改数组长度和删除数组元素等。具体算法如下:

1
2
3
4
5
6
7
8
9
10
11
int[] numbers = new int[100];
int[] selected = new int[10];

for (int i = 0, n = numbers.length; i < selected.length; i++) {
    int idx = (int)(Math.random() * n);    // 随机产生一个从0 - (n-1)的数字
    selected[i] = numbers[idx];
    numbers[idx] = numbers[n - 1];
    n--;    // 减1,从而在下次循环时产生的随机的numbers数组下标的范围从0 - (n-1)-1,
            // 保证了上一步中已经赋值给数组中其它数的numbers[n-1]不会在下次循环中给
            // 取得,确保了产生的数组selected中的数为不重复的。
}

Comments