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.
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
return sort(nums, 0, nums.size()-1, k);
}
int sort(vector<int>& nums, int low, int hight, int k) {
int flag = nums[hight];
int left = low;
int right = hight;
while(low < hight){
while(nums[low] >= flag && low < hight) low++;
nums[hight] = nums[low];
while(nums[hight] <= flag && low < hight) hight--;
nums[low] = nums[hight];
}
nums[low] = flag;
if(low == k-1) return flag;
else if(low < k-1) return sort(nums, low+1, right, k);
else return sort(nums, left, low-1, k);
}
};
Runtime: 28 ms, faster than 35.55% of C++ online submissions for Kth Largest Element in an Array.
Memory Usage: 9.8 MB, less than 21.26% of C++ online submissions for Kth Largest Element in an Array.
思路
- 快排（從大到小踱稍，選擇最后一個(gè)元素作為樞紐）
- 每一次迭代后比較樞紐的索引與k的大小
- index == k return nums[index]; index > k return sort(left area); index < k return sort(right area)
優(yōu)化
- heap？
- etc.
