Find the second highest item

Question

• In this array, how to find the values ​​2, 3, 4 or 5?

• Also, if we use the max() function in python, then what is the order of complexity ie associated with this max() function?

.

 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

I would go for:

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

This is more efficient than sorting the entire list and then using the first n element. See the heapq documentation for more information.

Answer 2

You can use sorted(set(element)) :

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

as a function:

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

Test:

 >>> 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 >>> 

Please note: here you only need to sort and delete duplicates once, if you are worried about performance, you can cache the result of sorted(set(li)) .

Answer 3

If performance is a problem (for example, you intend to call it a lot), then you should always keep the list sorted and deduplicated always, but just the first, second, or nth element (which is o(1) ).

Use bisect for this - it's faster than the "standard" sort .

insort allows insort to insert an element, and bisect allows you to find whether to insert at all (to avoid duplication).

---

If it is not, I would suggest a simpler one:

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

If reverse indexing looks ugly for you, you can do:

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

Answer 4

As for which method will have the lowest time complexity, it depends a lot on what types of requests you plan to make.

If you plan to make queries with high indices (for example, the 36th largest item in the list with 38 items), your nth_largest(li,n) function will be close to O (n ^ 2) time complexity, since this will need to be done max, which is O (n), several times. It will be similar to a sorting selection algorithm, with the exception of using max() instead of min() .

On the other hand, if you only make outstanding index queries, then your function can be effective, because it will only use the O (n) max function several times, and the time complexity will be close to O (n). However, creating the maximum heap is possible in linear O (n) time, and you would be better off just using this. After you encounter the problem of creating a heap, all your max() operations on the heap will be O (1), which may be the best long-term solution for you.

I believe that the most scalable way (in terms of being able to query the nth largest element for any n) is to sort the list with O (n log n) time complexity using the built-in sort function, and then make O (1) queries from a sorted list. Of course, this is not the most effective method in terms of memory, but in terms of time complexity, it is very effective.

Answer 5

If you do not mind using numpy ( import numpy as np ):

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

gives you the i-th largest list element with guaranteed worst case O (n) .

The partition(a, kth) methods return an array in which the element k th is the same as in the sorted array, all elements are smaller and all behind are larger.

Answer 6

What about:

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