题目描述
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
Example1:
输入: [3,2,1,5,6,4] 和 k = 2 输出: 5
Example2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4
说明
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
解题思路
- 快排的应用
- 需要重新计算 索引k的位置
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int size = nums.size();
if(k <= 0 || k > size){
return -1;
}
int begin = 0;
int end = size - 1;
int idx = 0;
k = nums.size() - (k - 1) - 1; // 这里需要重新计算一下下标的位置，5个元素，第2大下标其实是idx = 3
while(begin <= end){
idx = partition(nums, begin, end);
if(idx == k){
return nums[idx];
}else if(idx > k){
end = idx - 1;
}else{
begin = idx + 1;
}
}
return -1;
}
int partition(vector<int>& nums, int begin, int end){
int pivot = nums[begin];
while(begin < end){
while(begin < end && nums[end] >= pivot){
end--;
}
nums[begin] = nums[end];
while(begin < end && nums[begin] <= pivot){
begin++;
}
nums[end] = nums[begin];
}
nums[begin] = pivot;
return begin;
}
};
