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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int> pq; for(auto n:nums){ pq.push(-n); if(pq.size()>k) pq.pop(); } return -pq.top(); } }; class Solution_QS { int partition(vector<int>& nums, int l, int h){ int pivot = nums[h]; int i = l-1; for(int j=l; j<h; ++j){ if(nums[j]<=pivot){ swap(nums[++i], nums[j]); } } swap(nums[++i], nums[h]); return i; } int select(vector<int>& nums, int l, int h, int k){ if(l>h) return 0; int p = partition(nums, l, h); if(p==k) return nums[p]; if(p<k) return select(nums, p+1, h, k); else return select(nums, l, p-1, k); } public: int findKthLargest(vector<int>& nums, int k) { int n = nums.size(); k = n-k;//invert to incremental order return select(nums, 0, nums.size()-1, k); } }; |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | //Java, Quick Sort class Solution { void swap(int[] nums, int i, int j){ int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } int partition(int[] nums, int l, int r){ int pivot = nums[r]; int i = l; for(int j=l; j<r; ++j){ if(nums[j]<=pivot){ swap(nums, i, j); i++; } } swap(nums, i, r); return i; } int select(int[] nums, int l, int r, int k){ if(l>r) return 0; int p = partition(nums, l, r); if(p==k) return nums[p]; if(p<k) return select(nums, p+1, r, k); else return select(nums, l, p-1, k); } public int findKthLargest(int[] nums, int k) { return select(nums, 0, nums.length-1, nums.length-k); } } |
No comments:
Post a Comment