從N個數 N很大中隨機取k個不重複數有什麼方法？

1樓：夜清凌

計算機題目嗎？取數字放進Set裡？比如

while (k > 0)

random(1, N) = i；

set.put(i) = false? continue : k--;

2樓：程式設計思維

如果n很大，而k很小，比如在1億個數裡面挑5個數，random_shuffle()是對這n個數進行亂序，然後再找出5個數，速度當然會很慢，時間主要花在亂序上了。這種情況下完全可以隨機取乙個數，如果與已挑選的數不重複，就新增到已選資料的集合中，直到選取了K個數為止。

如果是在1億個數裡面挑8000萬個，那使用random_shuffle方法可能就會比較合適。

這是乙個很好的用於考驗程式設計師能否根據實際問題採用正確演算法的問題。關鍵是N很大是知道的，但K是多少如果是執行時才知道，那應該如何制訂策略。我的想法是應當把K的範圍分成幾個區間？

在不同區間採用什麼樣的演算法？能不能通過具體的測試來確定？

3樓：crystalzhiguo

生產k個不重複0-1的隨機數，然後放大N倍取整，將此5個數作為索引，對應索引處的數字即可。

取出後檢視是否重複，重複了幾個，就再用此方法取出來幾個，如此反覆，直到不重複。

以上方法比較適合N個數都在記憶體中，且以陣列方式儲存的情況。

如果是資料庫中的N個數，那就用sql語句最方便了。

要是寫在檔案裡面的N個數，就不太好說了，因為不清楚檔案是以什麼方式和格式儲存的。

要是資料儲存在鍊表等其他資料結構中，只能具體問題具體分析了。

4樓：

"取k個不重複數"是個簡單的演算法，很難有更好的演算法了。但你竟然用的是 std::random_shuffle/std::

shuffle，它們可不是N中只取K個，而是將N個都混亂了一下，顯然把時間複雜度從O(k)公升到了O(n)。你應該用 @大臭豬提到的std::sample。

若你的編譯器不支援std::sample，那就自己寫乙個，演算法是：從N個中隨機取乙個，移到尾部a[n-1]；從N-1個中隨機取乙個，移到尾部a[n-2]；從N-2個中隨機取乙個，移到尾部a[n-3]；…… 重複K次。

5樓：

如果 k 相對 n 足夠小，可以試試樸素的 O(k^2) 也就是隨機 n 裡面抽乙個，看看 k 個裡面有沒有重複。

複雜度就是 O(n) 你覺得慢那也是因為 n 很大。

沒有什麼好辦法，工程師的辦法只能讓隨機數變得更偽，比如事先生成一套隨機數表。

另外，random_shuffle 已經被 c17 移除了，最好用 shuffle，c17 的話可以用 sample。

從N個數 N很大 中隨機取k個不重複數有什麼方法？