Description

Find K-th largest element in an array.

Solution

Quick selection O(N)

class Solution:
   """
   @param n: An integer
   @param nums: An array
   @return: the Kth largest element
   """
   def quick_s(self,num,left,right,k):
       if left==right:
           return num[left]
       i=left
       j=right
       pivot = num[(i+j)//2]
       while i<=j:
           while i<=j and num[i]>pivot :
               i+=1
           while i<=j and num[j]<pivot:
               j-=1
           if(i<=j):
               tmp = num[i]
               num[i] = num[j]
               num[j] = tmp
               i+=1
               j-=1
       if left + k-1 <= j:
           return self.quick_s(num,left,j,k)
       elif left + k -1 >= i:
           return self.quick_s(num,i,right,k-(i-left))
       else:
           return num[j+1]
   def kthLargestElement(self, n, nums):
       # write your code here
       return self.quick_s(nums,0,len(nums)-1,n)