因爲它們產生

Question

我正在寫一個程序比需要找到一組號碼中的第N個最大的值算出一組號碼在第N個最大值。這些數字是由程序生成的，但我沒有足夠的內存來存儲N個數字。是否有比N更好的上限，可以存儲？這組數字（和N）的大小的上限約爲100,000,000。

注：數字是小數和列表可以包括重複。

[編輯]：我的內存限制爲16 MB。

Answer 1

這是一種多通道算法（因此，您必須能夠多次生成相同的列表，或將列表存儲到輔助存儲中）。

第一遍：

• 找到的最高值和最低值。這是你的初始範圍。第一後

通行證：

1. 除以的範圍內成10個等間隔箱。我們不需要在垃圾箱中存儲任何數字。我們只是要計算垃圾箱的會員資格。所以我們只需要一個整數數組（或者bigint - 任何可以準確地保存我們的計數的數值）。注意10是任意數量的分箱。您的樣本量和分佈將決定最佳選擇。
2. 通過旋轉數據中的每個數字，增加您看到的數量的二者之一的計數。
3. 找出哪個垃圾箱有答案，並將該垃圾箱上方的數字添加到獲獎垃圾箱上方的數字計數。
4. 獲獎箱的頂部和底部範圍是您的新範圍。
5. 再次循環這些步驟，直到您有足夠的內存來保存當前文件夾中的數字。

最後一關：

• 你應該知道有多少數字是當前二進制上面現在。
• 您有足夠的存儲空間來抓取當前垃圾箱範圍內的所有數字，因此您可以旋轉並獲取實際數字。只需對它們進行排序並獲取正確的編號。

例如：如果你看到的範圍是0.0到1000.0，你的垃圾箱的範圍將是：

(- 0.0 - 100.0] 
(100.0 - 200.0] 
(200.0 - 300.0] 
... 
(900.0 - 1000.0) 

如果你通過你的電話號碼爲（100.0計數發現 - 2000.0]斌，你的下集箱的將是：

(100.0 - 110.0] 
(110.0 - 120.0] 
etc. 

---

另一種多通道的想法：

只需進行二分查找。選擇範圍的中點作爲第一次猜測。你的通行證只需要做一個高於/低於計數來確定下一個估計值（可以通過計數來加權，或者爲簡化代碼而簡單地進行平均）。

Answer 2

如果我理解好，您的程序上限的內存使用情況是O（N）（可能N + 1）。您可以維護生成的值的列表，該列表比當前X（迄今爲止的第N個最大值）大，按照最低的順序排列。只要生成一個新的更大的值，就可以將當前的X替換爲列表的第一個元素，並將剛剛生成的值插入列表中的相應位置。

Answer 3

排序-n | uniq的-c和第N應該是第N行

Answer 4

這類似於另一個問題 - C Program to search n-th smallest element in array without sorting? - 在這裏你可以得到一些答案。
該邏輯將同樣適用於第N大/最小的搜索。
注意：我不是說這是重複的。

---

由於您有很多（接近10億？）數字，這裏是空間優化的另一種方法。
假設您的數字適合32位值，那麼大約10億將需要一段時間接近32GB的空間。現在，如果您可以承受大約128MB的工作內存，我們可以一次完成。

1. 想象存儲爲32位字的陣列1十億位向量
   • 讓它被初始化爲全零
   • 開始通過你的號碼運行並保持設定正確的位位置數的值
   • 當你與一個一遍完成，開始從該位向量開始計數第N集位
   • 該位的位置讓你的第N個數量最多
   價值
   • 實際上，你已經整理過程中的所有的數字（但是，重複的次數不跟蹤）

Answer 5

您能夠再生同一組從開始的數字？如果是的話，可以在輸出上多次傳遞：首先找到最大值，重新啓動發生器，找到最小的數字，重新啓動發生器，並重復此操作直到得到結果。

這將是一個真正的表現殺手，因爲你有很多數字，並且需要很多通行證 - 但是在記憶方面，你只需要存儲2個元素（當前最大值和一個「限制「，你在上一次傳球中找到的號碼）和一個傳球計數器。

您可以通過使用優先級隊列找到M個最大元素加快它（選擇數μm，你能夠裝入內存），讓您減少需要N/M的遍數。

如果您需要查找15個數字列表中的第10個最大元素，則可以通過其他方式節省時間。由於它是第10大元素，這意味着有15-10 = 5個元素比這個元素小 - 所以你可以找第6個最小的元素來代替。