找出第二高的元素

Question

1. 如何在给定的数组中找到第二、第三、第四或第五个值？

2. 如果我们在Python中使用max()函数，与此函数相关的复杂度是什么？

def nth_largest(li,n):   
    li.remove(max(li))
    print max(ele)  //will give me the second largest
    #how to make a general algorithm to find the 2nd,3rd,4th highest value
    #n is the element to be found  below the highest value

- Hulk

---

如果你有列表 [1,2,2]，你想要作为第二大元素的是什么？ 1 还是 2？ - DSM

我希望在你的情况下它是1。 - Hulk

Answer 1

我会选择：

import heapq
res = heapq.nlargest(2, some_sequence)
print res[1] # to get 2nd largest

相对于对整个列表进行排序，然后选取前n个元素，这种方法更加高效。查看heapq文档以获取更多信息。

- Jon Clements

---

max() 的复杂度是多少？ - Hulk

@ Hulk，你需要扫描两次列表才能找到“max”... 这个方法只需要扫描一次，并使用堆队列保留两个最大值。 - Jon Clements

由于他指定只想计算唯一元素（即[1,2,2]应返回1而不是2），因此您首先必须将列表转换为集合，以便得到预期的结果。 - Voo

但是导入也是一项昂贵的操作，为什么不使用内置的排序方法呢？ - Hulk

@JuanCatalan Jon 的意思是你需要扫描两次列表才能使用 max() 函数获取第二大的元素。 - kqr

Answer 2

你可以使用 sorted(set(element)) 来进行排序：

>>> a = (0, 11, 100, 11, 33, 33, 55)
>>>
>>> sorted(set(a))[-1] # highest
100
>>> sorted(set(a))[-2] # second highest
55
>>>

作为一个函数：

def nth_largest(li, n):
    return sorted(set(li))[-n]

测试：

>>> a = (0, 11, 100, 11, 33, 33, 55)
>>> def nth_largest(li, n):
...     return sorted(set(li))[-n]
...
>>>
>>> nth_largest(a, 1)
100
>>> nth_largest(a, 2)
55
>>>

注意，这里只需要对列表进行一次排序和去重，如果您担心性能问题，可以缓存sorted(set(li))的结果。

- user1129665

Answer 3

如果性能是一个问题（例如：你想经常调用此函数），那么你应该始终保持列表排序和去重，并简单地获取第一个、第二个或第n个元素（这是o(1)）。

使用bisect模块 - 它比“标准”sort更快。 insort允许您插入一个元素，而bisect将让您确定是否应该插入（以避免重复）。

---

如果不是，则建议使用更简单的方法：

def nth_largest(li, n):.
    return sorted(set(li))[-(n+1)]

如果反向索引看起来很丑陋，您可以进行以下操作：

def nth_largest(li, n):
    return sorted(set(li), reverse=True)[n]    

- Thomas Orozco

Answer 4

关于哪种方法会具有最低的时间复杂度，这在很大程度上取决于您计划进行哪些类型的查询。

如果您计划对高索引进行查询（例如，在具有38个元素的列表中查询第36个最大元素），则您的函数nth_largest(li,n)将具有接近O(n^2)的时间复杂度，因为它将不得不多次执行max，这是O(n)。它类似于选择排序算法，只是使用max()而不是min()。

另一方面，如果您只进行低索引查询，则您的函数可以是有效的，因为它只会几次应用O(n)的max函数，时间复杂度将接近O(n)。但是，建立最大堆可以在线性时间O(n)内完成，您最好只使用它。在经过构建堆的麻烦之后，堆上的所有max()操作都将是O(1)，这可能是您更好的长期解决方案。

我认为最可扩展的方法（就能够查询任何n的第n个最大元素而言）是使用内置的sort函数对具有O(n log n)时间复杂度的列表进行排序，然后从排序后的列表中进行O(1)查询。当然，这并不是最节省内存的方法，但就时间复杂度而言非常高效。

- Shashank

Answer 5

如果您不介意使用numpy（import numpy as np）：

np.partition(numbers, -i)[-i]

该函数返回列表中第 i 大的元素，并保证最差情况下运行时间为O(n)。

partition(a, kth) 方法返回一个数组，其中第k个元素在排序后的数组中位置相同，所有在它之前的元素都更小，在它之后的元素都更大。

- serv-inc

Answer 6

这样怎么样：

sorted(li)[::-1][n]

- Jo Are By

---

.reverse 是原地操作，不返回任何值。 - DSM

让我再试一次：你现在的代码无法工作，因为 li_s.reverse() 返回了 None，而 None[n] 没有意义。 - DSM

只需执行 sorted(li, reverse=True)[n]，无需在排序后翻转列表... - Jon Clements

说真的，“不要那么挑剔”？(a) 在Jon重写你的代码之前，你的解决方案根本就不起作用；(b) 成为一名优秀的开发人员就是要挑剔。告诉我们你在哪里工作，这样我们就可以避免乘坐任何由你编写控制系统的电梯。 - Chris Johnson

我自己重写了它。“不要挑剔”只是一个玩笑。不要太认真。 - Jo Are By