Menu
Hey. I have a very large array and I want to find the Nth largest value. Trivially I can sort the array and then take the Nth element but I'm only interested in one element so there's probably a better way than sorting the entire array...
340
Linear search can be used to search for the smallest or largest value in an unsorted list rather than searching for a match. It can do so by keeping track of the largest (or smallest) value and updating as necessary as the algorithm iterates through the dataset.
Using index We can design a for loop to access the elements from the list with the in clause applied for nth index.
Contruct the min binary heap from the array this operation will take O(n) time. Since this is a min binary heap, the element at the root is the minimum value. So keep on removing element frm root, till u get ur kth minimum value. o(1) operation.
In Python, you can sort a list using the built-in list. sort() method or the built-in sorted() function. The sorted() function creates a new sorted list, while the list. sort() method sorts the list in place.
A heap is the best data structure for this operation and Python has an excellent built-in library to do just this, called heapq.
import heapq
def nth_largest(n, iter):
return heapq.nlargest(n, iter)[-1]
Example Usage:
>>> import random
>>> iter = [random.randint(0,1000) for i in range(100)]
>>> n = 10
>>> nth_largest(n, iter)
920
Confirm result by sorting:
>>> list(sorted(iter))[-10]
920
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
