215 Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,

Given [3,2,1,5,6,4] and k = 2, return 5.

• Note: You may assume k is always valid, 1 ≤ k ≤ array's length.

Solution

class Solution {
public:
    int findK(vector<int>& nums, int k, int is, int ie) {
        // a quick sort step
        int pivot = nums[is];
        int i = is + 1, j = ie;
        while ( i <= j ) {
            if ( nums[j] > pivot ) swap(nums[j], nums[i++]);
            else j -= 1;
        }
        swap(nums[j], nums[is]);
        // the devision is between nums[j] / nums[i] now; nums[j] = pivot;
        if ( j+1 == k ) return pivot;
        if ( j+1 <= k-1 ) return findK(nums, k, i, ie);
        if ( j+1 >= k+1 ) return findK(nums, k, is, j-1);
        return 0;
    }
    int findKthLargest(vector<int>& nums, int k) {
        return findK(nums, k, 0, nums.size()-1);
    }
};

Note Quick sort! PRACTICE! Python quicksort code

def quicksort(nums, start, end):
  if ( start >= end ): return
  pivot = nums[start]
  i, j = start+1, end
  while ( i <= j ):
    if ( nums[i] < pivot ):
      nums[i], nums[j] = nums[j], nums[i]
      j -= 1
    else: i += 1
  nums[start], nums[j] = nums[j], nums[start]
  quicksort(nums, start, j-1)
  quicksort(nums, j+1, end)

We can also use heap to solve this problem. We maintain a minimum heap to store the top K largest elements. Whenever a new element i is added, compare it with the peak element (the minimum element in the heap).

• If i is larger than the peak element, push it to the heap, and pop out ( the peak element).
• Otherwise do nothing.