Re: [問題] 1-42取出6+1個數字
※ 引述《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
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 19 之 21 篇)：