找到未分類列表的第N個項目而不對該列表進行分類

嘿。我有一個非常大的數組，我想查找第N個最大值。平凡我可以排序陣列，然後採取第N個元素，但我只對一個元素感興趣，所以可能比排序整個陣列更好的方法...找到未分類列表的第N個項目而不對該列表進行分類

來源

2009-06-23 ooboo

排序將需要O（nlogn）在最小運行時 - 有非常有效的selection algorithms其可以在線性時間內解決問題。

Partition-based selection（有時Quick select），它是基於快速排序（遞歸分割）的想法，是一個很好的解決方案（參見鏈接，僞代碼+ Another example）。

來源

2009-06-23 20:12:07 Dario

尼斯鏈接。我相信這是最好的。 – 2009-06-23 20:26:02

不幸的是，現在鏈接「另一個例子」導致MIT的受保護網頁，您必須有權訪問。 – Beel 2013-02-10 05:48:47

使用heapsort。它只是部分排列列表，直到你畫出元素爲止。

來源

2009-06-23 20:07:22 UncleO

嘗試查找第n/2個元素 - 需要O（nlogn）！ – Dario 2009-06-23 20:13:42

您可以迭代整個序列，維護您找到的5個最大值的列表（這將是O（n））。這是說，我認爲這將是更簡單的排序清單。

來源

2009-06-23 20:07:52

但是，如果它不是第五個但是第n個元素，則會有O（n2），這比排序更糟糕。 – Dario 2009-06-23 20:10:12

我想你的意思是保持N個最大值的列表。但是在這種情況下，N不能太大。 – 2009-06-23 20:11:01

您基本上想要生成一個「前N」列表並選擇該列表末尾的列表。

因此，您可以掃描數組一次，並在largeArray項目大於top-N列表的最後一項時插入到一個空列表中，然後刪除最後一項。

掃描完成後，選取前N列表中的最後一項。

爲整數和一個實例N = 5：

int[] top5 = new int[5](); 
top5[0] = top5[1] = top5[2] = top5[3] = top5[4] = 0x80000000; // or your min value 

for(int i = 0; i < largeArray.length; i++) { 
    if(largeArray[i] > top5[4]) { 
     // insert into top5: 
     top5[4] = largeArray[i]; 

     // resort: 
     quickSort(top5); 
    } 
}

來源

2009-06-23 20:09:33

正如人們所說，一旦記錄了K個最大值，就可以遍歷列表。如果K很大，則該算法將接近於O（n ）。

但是，您可以將第K個最大值存儲爲二叉樹，並且操作變爲O（n log k）。

根據維基百科，這是最好的選擇算法：

function findFirstK(list, left, right, k) 
    if right > left 
     select pivotIndex between left and right 
     pivotNewIndex := partition(list, left, right, pivotIndex) 
     if pivotNewIndex > k // new condition 
      findFirstK(list, left, pivotNewIndex-1, k) 
     if pivotNewIndex < k 
      findFirstK(list, pivotNewIndex+1, right, k)

它的複雜度爲O（n）

來源

2009-06-23 20:18:55 Unknown

一個簡單的修改快速排序工作得很好實踐。它的平均運行時間與N成正比（儘管最壞的運行時間運行時間是O（N^2））。

繼續像快速排序。隨機選取一個數據透視值，然後通過數據流查看它們是高於還是低於該數據透視值，並根據該比較結果將它們放入兩個箱中。在快速排序中，您可以遞歸地對這兩個倉中的每一個進行排序。但是對於第N個最高值的計算，您只需要對其中一個箱進行排序。每個箱的總數告訴您哪個箱保存了您的第n個最高值。因此，例如，如果您想要第125個最高值，並且您分爲兩個箱，其中「高」箱中有75個，「低」箱中有150個，則可以忽略高箱，然後繼續查找125-75 =僅在低檔箱中爲第50個最高值。

來源

2009-06-23 20:23:03 SPWorley

堆是這個操作的最佳數據結構，Python有一個很好的內置庫來完成這個工作，叫做heapq。

import heapq 

def nth_largest(n, iter): 
    return heapq.nlargest(n, iter)[-1]

實例應用：

>>> import random 
>>> iter = [random.randint(0,1000) for i in range(100)] 
>>> n = 10 
>>> nth_largest(n, iter) 
920

確認結果通過排序：

>>> list(sorted(iter))[-10] 
920

來源

2009-06-24 03:21:47 FogleBird

你可以嘗試的方法中位數中位數 - 它的速度是O（N）。

來源

2010-01-25 03:07:17 user183037

如果這是生產代碼，你應該做的一件事是測試你的數據樣本。例如，您可能會考慮1000或10000個元素的「大」數組，並從配方中編寫快速選擇方法。

已排序的編譯特性及其隱藏性和不斷髮展的優化使其比中小型數據集上的Python快速選擇方法更快（< 1,000,000個元素）。此外，您可能會發現，如果將數組的大小增加到超過該數量，則內存在本機代碼中的處理效率會更高，並且益處會持續下去。因此，即使quickselect是O（n）與已排序的O（nlogn），也不會考慮處理每個n元素的實際機器代碼指令的數量，對流水線的任何影響，處理器緩存的使用以及其他排序的創建者和維護者將會烘烤到Python代碼中。

來源

2016-02-11 01:28:32

找到未分類列表的第N個項目而不對該列表進行分類

回答

相關問題