Re: [問題] 1-42取出6+1個數字
(舉手) 問幾個問題...
這個看起來是從陣列最後方, 隨機選一個之前的元素跟後面的置換.
然後把整個陣列 n 跑完之後, 取前面的 m 個...
那為什麼不直接後面作 m 次以後直接取後面的 m 個呢?
另外取前面 n 個, 第一個會永遠不可能是自己吧?
最後感謝你提供 (對我來說) 如此易於了解的方法.
※ 引述《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)。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.25.148.49
討論串 (同標題文章)