找到第二个最高的元素

Question

1. 在给定的数组中如何找到第2,3,4或5个值？

2. 另外，如果我们在python中使用max()函数，那么复杂度的顺序是什么，即与这个函数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 

Answer 1

我会去：

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

这比排序整个名单，然后采取第一n许多元素。有关更多信息，请参阅heapq documentation。

Answer 2

如何：

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

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]  

Answer 4

你可以使用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))的结果。

Answer 5

至于哪种方法的时间复杂度最低，这取决于您计划制作哪些类型的查询。

如果您打算对高索引（例如，包含38个元素的列表中的第36个最大元素）进行查询，则函数nth_largest(li,n)将接近O（n^2）时间复杂度，因为它必须执行最大值，这是O（n），几次。除了使用max()而不是min()之外，它与选择排序算法类似。另一方面，如果你只做低索引查询，那么你的函数可以很有效率，因为它只会多次应用O（n）max函数，并且时间复杂度将接近于O（n ）。然而，在线性时间O（n）中建立一个最大堆是可能的，你最好使用它。在经历构建堆的麻烦之后，堆上的所有max()操作都将是O（1），这对您来说可能是更好的长期解决方案。

我相信最易扩展的方式（在能够查询第N个元素任何 n项）是排序与时间复杂度为O使用列表中（N log n）的内置sort函数，然后从排序列表中进行O（1）个查询。当然，这不是最有效的内存方法，但在时间复杂度方面它非常高效。

Answer 6

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

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

给你the ith largest element of the list with a guaranteed worst-case O(n) running time。

partition(a, kth)方法返回一个数组，其中k th元素是相同的，它将在一个有序数组中，前面的所有元素都较小，并且后面的所有元素都较大。