给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。输入第一行为数组,-1为结束标志,第二行为k值。输出第k大个元素。
时间: 2024-03-16 16:47:32 浏览: 29
好的,这是一个找第k大元素的问题,可以使用快速选择算法来解决。具体步骤如下:
1. 定义一个快速选择函数,输入为数组和目标排名k。
2. 对数组进行快速排序,选择一个基准值pivot,将小于pivot的元素放在左边,大于pivot的元素放在右边。
3. 如果目标排名k等于基准值的排名(即基准值是第k大元素),则返回基准值。
4. 如果目标排名k小于基准值的排名,则在左半部分递归调用快速选择函数。
5. 如果目标排名k大于基准值的排名,则在右半部分递归调用快速选择函数。
6. 重复上述步骤,直到找到第k大元素。
下面是代码实现,可以参考一下:
```
#include <iostream>
#include <vector>
using namespace std;
int partition(vector<int>& nums, int left, int right) {
int pivot = nums[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (nums[j] >= pivot) {
i++;
swap(nums[i], nums[j]);
}
}
swap(nums[i+1], nums[right]);
return i+1;
}
int quickSelect(vector<int>& nums, int left, int right, int k) {
int index = partition(nums, left, right);
if (index == k-1) {
return nums[index];
} else if (index < k-1) {
return quickSelect(nums, index+1, right, k);
} else {
return quickSelect(nums, left, index-1, k);
}
}
int main() {
vector<int> nums;
int num, k;
cin >> num;
while (num != -1) {
nums.push_back(num);
cin >> num;
}
cin >> k;
int result = quickSelect(nums, 0, nums.size()-1, k);
cout << result << endl;
return 0;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)