c++查找第k大的元素
时间: 2024-02-12 22:03:58 浏览: 31
可以使用快速选择算法来查找第k大的元素,其时间复杂度为O(n)。
快速选择算法的基本思路是:利用快速排序的思想,每次选取一个枢轴元素,将序列分为左右两部分,如果枢轴元素的下标为k-1,则该元素即为第k大的元素;如果枢轴元素的下标小于k-1,则在右半部分继续查找第k大的元素;如果枢轴元素的下标大于k-1,则在左半部分继续查找第k大的元素。
以下是C++代码实现:
```c++
int quickSelect(vector<int>& nums, int left, int right, int k) {
int pivot = nums[left], l = left, r = right;
while (l < r) {
while (l < r && nums[r] <= pivot) r--;
if (l < r) nums[l++] = nums[r];
while (l < r && nums[l] >= pivot) l++;
if (l < r) nums[r--] = nums[l];
}
nums[l] = pivot;
if (l == k - 1) return pivot;
else if (l < k - 1) return quickSelect(nums, l + 1, right, k);
else return quickSelect(nums, left, l - 1, k);
}
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
return quickSelect(nums, 0, n - 1, n - k + 1);
}
```
其中,left和right表示待查找的序列的左右边界,k表示要查找的元素的下标(即第k大的元素的下标为n-k)。pivot表示枢轴元素,l和r是左右指针,用于交换元素。函数quickSelect返回第k大的元素的值。函数findKthLargest用于调用quickSelect函数,计算第k大的元素的值。
使用方法:
```c++
vector<int> nums = {3, 2, 1, 5, 6, 4};
int k = 2;
int kthLargest = findKthLargest(nums, k);
cout << "The " << k << "th largest element is: " << kthLargest << endl;
```
输出结果:
```
The 2th largest element is: 5
```