algorithm - 给定 n 个数字中的最小和最大 10 个数字

Question

您能否建议一种有效的算法来从一组给定的 n 个数字(未排序)中找出最小 10 个和最大 10 个数字？

我想到的一种方法是对数组进行排序，然后进行选择。

应该有更好的方法来做到这一点。

你能推荐一种方法吗？

这不是作业题。

Answer 1

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

更新 步骤替换了现有的 smallest-of-the-largest-already-seen 和 largest-of-the-thmallest-already-seen。

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