题目描述
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
解题思路
- STL排序，返回下标为k-1的值即可
- 注意sort重载的函数，greater
(),表示从大到小排 - less
()，表示从小到大排（默认）
排序版本
C++代码
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end(), greater<int>());
return nums[k - 1];
}
};
快排解题思路
- 主要是快排算法的应用
- 选择枢纽，从左到右找第一个比枢纽大的
- 从右到左，找第一个比枢纽小的
- 交换两个指针指向的值的位置
- 交换枢纽与指针重合的位置
- 返回枢纽，如果此时的枢纽等于k，直接返回
- 如果小于k，left等于枢纽+1
- 否则，right等于枢纽-1
快排版本
C++代码
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
if(nums.size() == 0 || k <= 0 || k > nums.size()){
return -1;
}
int begin = 0;
int end = nums.size() - 1;
k = nums.size() - k;
while(begin <= end){
int index = partition(nums, begin, end);
if(index > k){
end = index - 1;
}else if(index < k){
begin = index + 1;
}else{
return nums[index];
}
}
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;
}
};
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int left = 0;
int right = nums.size() - 1;
k = nums.size() - (k - 1) - 1;
while(left <= right){
int pos = partition(nums, left, right);
if(pos == k){
return nums[pos];
}else if(pos < k){
left = pos + 1;
}else{
right = pos - 1;
}
}
return -1;
}
private:
int partition(vector<int>& nums, int left, int right){
int pivot = left;
int l = pivot + 1;
int r = right;
while(l <= r){
while(l <= right && nums[l] <= nums[pivot]){
l++;
}
while(r >= left && nums[r] > nums[pivot]){
r--;
}
if(l < r){
swap(nums[l], nums[r]);
}
}
swap(nums[pivot], nums[r]);
pivot = r;
return pivot;
}
};
