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.
Example 1:
Input: [3,2,1,5,6,4]
and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6]
and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
You may assume k is always valid, 1 ≤ k ≤ array's length.
A:
--------用maxHeap ---------O(n+k*log(k))-----------------class Solution { public: int findKthLargest(vector<int>& nums, int k) { int n = nums.size(); // need a min heap, thus the top() is the minimum to remove priority_queue<int, vector<int>, greater<int> > q; // default is less, which result into max queue for(auto v : nums) { q.push(v); if(q.size()>k) q.pop(); } return q.top(); } };
QuickSelect
(这道题的关键点在于 当值全部大于(或小于)pivot点的时候的处理方式。--》 因此要把pivot点swap到中间的操作。
class Solution {public:int findKthLargest(vector<int>& nums, int k) {// half of the quick sortint n = nums.size();if(k == 1){auto max_iter = max_element(nums.begin(), nums.end());// get maxreturn *max_iter;}int mid = (nums.front() + nums.back()) / 2;// first get mid of first and lastvector<int> bigger, smaller;int midCount = 0;for(const auto & val : nums){if( val > mid){bigger.push_back(val);// move to new and pop it out}else if(val == mid){midCount++;}else{smaller.push_back(val);}}if(bigger.size()>=k){return findKthLargest(bigger, k);}else if(bigger.size() + midCount >= k){return mid;}else{return findKthLargest(smaller, k- bigger.size() - midCount);}}};
这个题目,自己第一次做的时候, 没有做把end的值swap到mid位置的操作,因此会出现死循环。
Mistakes:
1: 当k ==1的时候,还是要继续分下去。 而基础条件应该是 start == end
2:
double pivot = (A[start] + A[end])/2;这里,当A[start] == 1, A[end]==2的 时候,pivot 的结果是1. !!!!!
因此要除以 2.0
------------------------排序------- 但是对于太大的数组,不适合--------------------
class Solution { public: int findKthLargest(vector<int>& nums, int k) { sort(nums.begin(), nums.end()); return nums[nums.size()-k]; } };
What do you think of using priority queue to solve this problem?
ReplyDelete