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

Question

你能推荐一个有效的算法来从一组给定的 n 个数字（未排序）中找出最小 10 个和最大 10 个数字吗？

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

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

你能推荐一个方法吗？

这不是作业题。

Answer 1

你可能想多了，你只需要扫描一次数组，通过比较最大的最小值和最小的最大值，将它填充到跟踪10个最小值和10个最大值的两个数组中。 O(n)

一个排序的复杂度为 O(n log n)

Answer 2

是的。制作两个大小为 k (k=10) 的堆，一个使用 less 作为比较器，第二个使用 more。两个有两个结构，将存储 "top k" 个元素。

遍历每个元素并放入每个堆中。如果元素出堆，忘记它们，这意味着它们不在前 10。

我相信这是一种叫做 Hadian-Sobel 算法的变体。它是堆排序的基础。有点像用于快速排序的分区（我相信是 Hoare 算法）。顺便说一句，也可以在这里使用。

这样你就可以得到 O(n) * 2 O(log k)。 N 个元素乘以大小 k 的两倍 heap_insert。这是 O(n log k)，对于 k=10.

基本上是线性的

Answer 3

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

Answer 4

您可以使用快速 select 算法解释 here 从未排序的整数数组中找到第 k 个最大的数字。之后，您可以再次迭代数组并检查大于第 k 个最大元素的元素。所以在两次迭代中你可以找到前 k 个元素。同样，您可以应用此方法来查找最小的 k 个元素。

离子排名算法的时间复杂度在一般情况下为 O(n)，其中 n 是数组中的元素数。第二次遍历数组也需要 O(n) 时间。因此整体复杂度也将是 O(n).

此算法运行比使用堆的方法更快。因为使用该方法的时间复杂度将为 O(nlogk)。

Answer 5

如果您正在使用 java，您可以使用 Treemap http://java.sun.com/javase/6/docs/api/java/util/TreeMap.html。

键的顺序是可以排序的，在遍历键的时候，你可以期望它们是有序的。

时间复杂度为 O(n)

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

Minimum and maximum 10 numbers from given n numbers

sorting

algorithm

max

minimum