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

问题描述：

您能否提出一个有效的算法来从一组给定n个数字（未分类）中找到最小10个和最大10个数字？我想到的给定n个数字中的最小和最大10个数字

的一种方式将是对数组进行排序，然后从中挑选。

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

你能提出一种方法吗？

这不是一个家庭作业问题。

@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

答

你可能会想太多，你只需要一次扫描阵列和commparing的最大最小值和最大值最低它填补两个阵列跟踪10个最小值和10米的最大值。 O（n）

A sort has O（n log n）

答

是的。创建两个大小为k（k=10）的堆，其中一个用less作为比较器，另一个用more。两个有两个存储“top k”元素的结构。

查看每个元素并放入每个堆中。如果要素走出去堆的，忘记他们，这意味着他们不是在排名前10位

我相信这是所谓的Hadian - 索贝尔算法的一些变化。这是堆排序的基础。有点像分区（我相信霍尔算法）快速排序。这也可以用在这里顺便说一句。

这样你O(n) * 2 O(log k)。 N元素次数heap_insert大小k。这是O(n log k)，对于k=10基本上是线性的。

答

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

选择排名算法的时间复杂度是在平均情况下，其中n是阵列中的元素的数目为O（n）。第二次遍历数组也需要O（n）次。因此总的复杂性也将是O（n）。

该算法运行速度快于使用堆的方法。因为使用这种方法时间复杂度将是O（nlogk）。

答

如果您使用的是Java您可以使用Treemap http://java.sun.com/javase/6/docs/api/java/util/TreeMap.html。

可以对键的顺序进行排序，并且当遍历键时，可以预期它们将按顺序排列。

此时间复杂度是O（n）

建议的算法是什么？ – greybeard

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

相关推荐