215. Kth Largest Element in an Array

A naive solution will be sort the array and return the (k-1)th number.
However, my intuition is the set up the heap for this array and pop out k-1 times.

1:  class Solution {  
2:  public:  
3:    int findKthLargest(vector<int>& nums, int k) {  
4:      priority_queue<int> pq(nums.begin(), nums.end());  
5:      for (int i = 0; i < k - 1; i++)  
6:        pq.pop();   
7:      return pq.top();  
8:    }  
9:  };  

I revisited the quicksort algorithm and found it is very useful for this problem. We just need to focus on the left partition which is less than the pivot. When the left partition size reaches nums.size()-k, the pivot is the kth largest number. Well. the OJ time seems slower than the heap algorithm. But I believe in general it is faster than the heap which is O(NlogN).

1:  class Solution {  
2:  public:  
3:    int findKthLargest(vector<int>& nums, int k) {  
4:      k = nums.size() - k;  
5:      int lo = 0;  
6:      int hi = nums.size()-1;  
7:      while (lo < hi) {  
8:        int j = partition(nums, lo, hi);  
9:        if (j == k) break;  
10:        else if (j < k) lo = j+1;  
11:        else hi = j-1;  
12:      }  
13:      return nums[k];  
14:    }  
15:    int partition(vector<int> &nums, int lo, int hi) {  
16:      int i = lo;  
17:      int j = hi+1;  
18:      while (1) {  
19:        while (i < hi && nums[++i] < nums[lo]);  
20:        while (j > lo && nums[--j] > nums[lo]);  
21:        if (i >= j) break;  
22:        swap(nums[i], nums[j]);  
23:      }  
24:      swap(nums[j], nums[lo]);  
25:      return j;  
26:    }  
27:  };