Python|寻找最大最小的N个元素几种方法



实际的生产中,常常会需要处理一个序列,找出其中的N个最大或者最小的元素,这里提供几种思路,不同的情况,使用不同的搜索方式,可以更好提高我们代码的运行效率。

“这里先假设目标序列的元素总数为S ”

N如果是1

如果只是简单地想找到最小或最大的元素,那么min()max()是最合适的选择。

    min([1,2,3]) #1
    max([1,2,3]) #3

N如果想对S比较小

这种情况最高效的方式是使用函数nlargest()nsmallest()

    import heapq
    heapq.nlargest(N, nums) #最大的N个元素组成的列表
    heapq.nsmallest(N, nums) #最小的N个元素

对于N较小的情况,还有一种高效的方式是下面这样:

heapq的方式,这种方式首先会在底层将数据转为成列表,且元素会以堆得顺序排列。

Python nums = [2,4,52,6,90,1] import heapq heap = list(nums) heapq.heapify(heap) heap [out]:[1, 4, 2, 6, 90, 52]

堆最重要的特性就是 heap[0]永远是最小的那个元素。接下来的元素,可以依次通过heapq.heappop()方法找到,这个方法会将第一个元素,也就是最小的元素弹出,然后以第二小的元素代替。这种操作的复杂度为O(logN)

    heapq.heappop(heap)
    [out]:1
    heapq.heappop(heap)
    [out]:2

如果N和S相近

这种情况下,通常更快的方法是先对集合排序,然后做切片操作。

    sorted(nums)[:N]
    #或者
    sorted(nums)[-N:]

  • 版权声明:欢迎转载,请注明出处
  • 发表日期:2017-09-15
  • 博客地址:blog.vimiix.com

Discuss

Scroll to top