Kth Largest Element in an Array
题目代码块想法
Description
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.
For example, Given [3,2,1,5,6,4] and k = 2, return 5.
代码
using namespace std;
class Solution {
public:
int findKthLargest(
vector<int>& nums,
int k) {
int left =
0;
int right = nums.size()-
1;
while(
1){
int pos = partition(nums,left,right);
if(pos == k-
1) {
cout<<k-
1<<endl;
return nums.at(pos);
}
else if(pos < k-
1){
left = pos+
1;
}
else{
right = pos -
1;
}
}
}
int partition(
vector<int>& nums,
int left,
int right){
int med = nums.at(left);
int left_record = left;
left = left +
1;
while(left <= right){
if(nums.at(left) < med && nums.at(right) > med){
int temp = nums.at(left);
nums.at(left) = nums.at(right);
nums.at(right) = temp;
left++;
right--;
}
if (nums.at(left) >= med){
left ++;
}
if(nums.at(right) <= med){
right--;
}
}
swap(nums[left_record], nums[right]);
return right;
}
};
想法
要要计算第k个最大值，通过快速排序的思想，选取一个中枢值，比中枢值小的放在右边，大的放在左边，返回中枢值位置，如果中枢值刚好是第k个，取其值为答案，如果中枢值位置比k小，说明要选取中枢值位置右边的值，那么进行的排序从pos+1开始，到end，重复上述步骤，如果中枢值位置比k大，说明要选取中枢值位置左边的值，重复上述步骤位置从left开始，到pos-1.
参考地址：https://www.cnblogs.com/grandyang/p/4539757.html
