LintCode: Kth Largest Element

Find K-th largest element in an array.

Note

You can swap elements in the array

Example

In array [9,3,2,4,8], the 3th largest element is 4

 
class Solution {
public:

   void swap(vector &A, int i, int j)
   {
       int t = A[i];
       A[i] = A[j];
       A[j] = t;
   }
   
   int helper(vector A, int k, int start, int end) 
   {
       int left = start+1, right = end;
       while(left <= right) {
           while(left <= right && A[left] >= A[start]) left++;
           while(left <= right && A[right] <= A[start]) right--;
           
           if (left < right) swap(A, left, right);
       }
       
       swap(A, start, right);
       
       if (right+1 == k) return A[right];
       else if (right+1 > k) return helper(A, k, start, right-1);
       else return helper(A, k, right+1, end);
   }
   
   
    /*
     * param k : description of k
     * param nums : description of array and index 0 ~ n-1
     * return: description of return
     */
    int kthLargestElement(int k, vector nums) {
        if ( k < 1 || k > nums.size()) return -1;
        return helper(nums, k, 0, nums.size()-1);
    }
};

 
class Solution {
   void swap(vector<int> &A, int i, int j)
   {
       int t = A[i];
       A[i] = A[j];
       A[j] = t;
   }
   
   void minHeapify(vector<int> &A, int N, int i)
   {
       int  l = 2*i, r = 2*i+1;
       int smallest = i;
       if (l < N && A[l] < A[smallest])
          smallest = l;
          
       if (r < N && A[r] < A[smallest])
          smallest = r;  
       
       if (smallest != i)
       {
           swap(A, i, smallest);
           minHeapify(A, N, smallest);
       }       
   }
   
   void buildMinHeap(vector<int> &A, int N)
   {
       for(int i = N/2; i>=0; i--)
           minHeapify(A, N, i);
   }
   
    /*
     * param k : description of k
     * param nums : description of array and index 0 ~ n-1
     * return: description of return
     */
    int kthLargestElement(int k, vector<int> nums) {
        vector<int> minHeap(k);
        
        for(int i = 0; i < k; i++)
           minHeap[i] = nums[i];
        
        buildMinHeap(minHeap, k);
        
        for(int i = k; i < nums.size(); i++){
            if (nums[i] > minHeap[0]){
                minHeap[0] = nums[i];
                minHeapify(minHeap, k, 0);
            }
        }        
        return minHeap[0];
    }
};