給定n個數字中的最小和最大10個數字

您能否提出一個有效的算法來從一組給定n個數字（未分類）中找到最小10個和最大10個數字？我想到的給定n個數字中的最小和最大10個數字

的一種方式將是對數組進行排序，然後從中挑選。

應該有更好的方法來做到這一點。

你能提出一種方法嗎？

這不是一個家庭作業問題。

來源

2015-09-13 Sakshi Malhotra

@Claudiu技術上我認爲只有局部排序算法可以通過OP使用。鏈接覆蓋它，但選擇只處理「第k」個最大數量，而不是「top-k」項目。雖然前者可以減少到後者，但我不確定是否可以採用其他方式來放棄複雜性。 – luk32

Python標準庫有這個工作，已經進行（heapq.nlargest和heapq.smallest）。

對於你的情況，它會制定出製作最小堆和最大堆與數據集的第10名成員預填充，然後進行在數據單次，必要時更新堆：

FOR element IN remaining_data 
    IF element > top_of_min_heap 
    THEN update_min_heap(element) 
    ENDIF 

    IF element < top_of_max_heap 
    THEN update_max_heap(element) 
    ENDIF 
ENDFOR

的更新步取代現有的，最小的已經見過最大的最十最小的最十大，已經看到和。

這裏大致是Python標準庫中的代碼是什麼樣子：

def nlargest(n, iterable): 
    """Find the n largest elements in a dataset.                     

    Equivalent to: sorted(iterable, reverse=True)[:n]                   
    """ 
    if n < 0: 
     return [] 
    it = iter(iterable) 
    result = list(islice(it, n))  # pre-populate with the first n elements 
    if not result: 
     return result 
    heapify(result)     # arrange them into a minheap 
    for elem in it:     
     if element > result[0]:  # new elem is bigger than the smallest-of-the-large 
      heapreplace(result, elem) # replace top element with new element 
    result.sort()      # sort the top ten 
    return result

來源

2015-09-14 00:18:41