给定一个大小为n(1≤n≤1000000)且无序的整型数组,数组中可能存在相同元素,请找出该数组第k(1≤k≤n)小的元素,注意这里的第k小元素指的是按从小到大排序后的第k个位置上的元素。的代码
时间: 2024-02-18 15:01:13 浏览: 82
可以使用快速选择算法来解决这个问题,其时间复杂度为O(n)。
快速选择算法的基本思想是利用快速排序的思想,每次选择一个pivot元素,将数组划分为两部分,一部分比pivot小,另一部分比pivot大。然后根据pivot的位置与k的大小关系,递归处理左半部分或右半部分,直到找到第k小的元素。
以下是代码实现:
```
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int quickSelect(vector<int>& nums, int k, int left, int right) {
if (left == right) return nums[left];
int pivot = nums[left + (right - left) / 2];
int i = left, j = right;
while (i <= j) {
while (nums[i] < pivot) i++;
while (nums[j] > pivot) j--;
if (i <= j) {
swap(nums[i], nums[j]);
i++;
j--;
}
}
if (left + k - 1 <= j) return quickSelect(nums, k, left, j);
if (left + k - 1 >= i) return quickSelect(nums, k - (i - left), i, right);
return nums[j + 1];
}
int main() {
int n, k;
cin >> n >> k;
vector<int> nums(n);
for (int i = 0; i < n; i++) cin >> nums[i];
cout << quickSelect(nums, k, 0, n - 1) << endl;
return 0;
}
```
其中,`quickSelect`函数用于寻找第k小的元素,`left`和`right`表示搜索范围。在每次递归中,首先选择pivot元素,将数组划分为两部分,然后判断pivot的位置与k的大小关系,递归处理左半部分或右半部分。最终返回第k小的元素。