Search code examples
pythonarraysalgorithmfindelement

Find 3rd largest element in an array without sorting

I have these similar kinds of questions over and over again in python. I want to master the way to solve this kind of problem. Please help me.

The questions are like "Find the 3rd largest (or 2nd largest or sometimes kth largest) element(or item) in an array without sorting" sometimes there comes another condition "with a minimum number of comparison" or "in O(n) time". How do I approach? or how to write an algorithm for this?

Thanks!

Solution

  • Change n to the corresponding number if you don't want the 3rd largest.

    largest[0] is the nth largest number.

    n=3
haystack=[1,2,3]
largest=[0]*n
for a in haystack:
    k=n
    for i in range(n):
        if a<=largest[i]:
            k=i
            break
    if k:
        k-=1
        for j in range(k):
            largest[j]=largest[j+1]
        largest[k]=a