Leetcode: Kth Largest Element in an Array (4ms)

Difficulty: Medium

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.

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

Hide Tags

 Divide and Conquer Heap

--------------------------------------------------------------------

Basically using the similar procedure in Quick Sort.
The good thing here is that we don't need to sort the whole array, we only need to sort part of the array until we found the Kth biggest one by revising the Quick Sort a little bit. So in the codes, we revised the quick sort to fit this problem.

NOTE: the quick should use pointers to transport the array, otherwise the space will exceed the limit.

/////////////////////////////////////////////
//codes

class Solution {

 public:

        //revised quick sort

        vector<int> QuickSort(vector<int>& s, int first, int last, int k){

               // s[first, last] -- is part of the data in s that needs to be sorted.

               int lower = first + 1, upper = last, bound = s[(last + first) / 2], len = s.size();

               //put the bound (middle one) in the first place

               //to ensure that it's not moved around. Later it

               //will be moved back

               swap(s[first], s[(last + first) / 2]);

               //swap according to bound

               while (lower <= upper){

                      while (s[lower] < bound){

                            lower++;

                      }

                      while (s[upper] > bound){

                            upper--;

                      }

                      if (lower < upper) swap(s[lower++], s[upper--]);

                      else lower++;

               }

               //move bound back to it's proper position

               swap(s[first], s[upper]);

               //partition and call quicksort, the previous bound is not counted in.

               if (first < upper - 1 && k>len - upper) s = QuickSort(s, first, upper - 1, k);

               if (upper + 1 < last && k<len - upper) s = QuickSort(s, upper + 1, last, k);

               return s; //up to now, the input s has been sorted!

        }

        //-----------------------------------------------

        int findKthLargest(vector<int>& nums, int k) {

               vector<int> fn = QuickSort(nums, 0, nums.size() - 1, k);

               return fn[nums.size() - k];

        }

 };