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.

思路一：  利用top-k的思想，这里可以用优先队列或者muiti-set来实现。O（Nlogk）

class Solution {public:    int findKthLargest(vector
     
      & nums, int k) {        priority_queue
      
        pq(nums.begin(), nums.end());        for (int i = 0; i < k - 1; i++)            pq.pop();         return pq.top();    }};
      
     

class Solution {public:    int findKthLargest(vector
     
      & nums, int k) {        multiset
      
        mset;        int n = nums.size();        for (int i = 0; i < n; i++) {             mset.insert(nums[i]);            if (mset.size() > k)                mset.erase(mset.begin());        }        return *mset.begin();    }};
      
     

思路二： 基于partition 函数的思路，算法复杂度O(N)

class Solution { public:    int partition(vector
     
      & nums, int left, int right) {        int pivot = nums[left];        int l = left + 1, r = right;        while (l <= r) {            if (nums[l] < pivot && nums[r] > pivot)                swap(nums[l++], nums[r--]);            if (nums[l] >= pivot) l++;             if (nums[r] <= pivot) r--;        }        swap(nums[left], nums[r]);        return r;    }        int findKthLargest(vector
      
       & nums, int k) {        int left = 0, right = nums.size() - 1;        while (true) {            int pos = partition(nums, left, right);            if (pos == k - 1) return nums[pos];            if (pos > k - 1) right = pos - 1;            else left = pos + 1;        }    }};
      
     

 follow up :

如果是要求第三大的数？

 

利用三个指针，基于top-3 的思想。