作者superlubu (劲过吕布)
看板java
标题Re: [问题] 1-42取出6+1个数字
时间Sat Jul 22 08:21:20 2006
※ 引述《zanyking (遥远的旅人)》之铭言：
: 1-42 取 7用set 的 Contains判断不取重复可能还好。
: 1-20000 取 10000呢？你很快就会觉得是不是掉进无穷回圈当中了。
: (如果你不幸用递回写，哪很快就会stack Over Flow了。)
: 之前Trace JDK程式码时有看到一个好方法给大家参考。
: 原理如下：
: 假设阵列长度n，随机取m个。
: for(int i = arr.length-1;i>=0;i--)
: {
: int randPosition = Random.getInt(i);//取得0~i之间的随机整数。
: Swap(arr[i], arr[randPosition]);//替换值。
: }
: return arr[0]~ arr[m-1];
: 不考虑Random的实作效能的话，程式效率为O(n)。
从你这一个方法，我倒想到了一个较另类的高效方法 :P
假设阵列长度 n, 随机取 m 个
int arr[] = new int[n];
for (int i = 0; i < n; i++) arr[i] = i; // initialize
int result[] = new int[m];
for (int i = 0; i < m; i++)
{
int pos = Random.nextInt(n-i); // get the position from 0 - (n-i-1)
result[i] = arr[pos];
if (pos != n-i-1) {
Swap(arr[n-i-1], arr[pos]);
}
}
return result;
只需 loop m 次就可以得到不重覆的 m 个数字了 :D
--
《为了要得到真相，就要向原 PO 伸图》
那就是伸图魔人的没图没真相原则，那时我们坚信那就是逼逼死的真实
靠么，图咧？
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 219.79.40.97