题目描述
给定一个长度为n的整数数列,以及一个整数k,请用快速选择算法求出数列的第k小的数是多少。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数(所有整数均在1~109范围内),表示整数数列。
输出格式
输出一个整数,表示数列的第k小数。
数据范围
1≤n≤1000000,
1≤k≤n
样例
输入样例:
5 3
2 4 1 5 3
输出样例:
3
算法1
类似于快速排序的思想,在每次完成一次划分之后,可以判断要寻找的第k大的数也就是数组坐标k-1的与每次的划分点j分界线的大小,由于每趟快排分界点的数都放在了最终排序后的位置,当[k-1]小于等于j时,此时要寻找的第k大的数字位于j前面的区域,根据二分的思想,可以得知k必定不在j之后的区域,因此只对前面部分排序,反之则直对后面部分排序,弱l=r说明只有一个元素,便是我们要找的k大的值
时间复杂度分析:O(n)
第一次扫描一遍n次,第二趟平均n/2次,第k次平均n/(2^k)次,这一级数和收敛,因此时间复杂度还是O(n)
C++ 代码
#include<iostream>
#include<vector>
using namespace std;
int quick_sort(vector<int> &q,int l,int r,int k){
if(l>=r) return q[r];
int i=l-1,j=r+1,x=q[l];
while(i<j){
do i++; while(x>q[i]);
do j--; while(x<q[j]);
if(i<j) swap(q[i],q[j]);
else break;
}
if(j>=k-1)quick_sort(q,l,j,k);//因为第k大对应下标为k-1
else quick_sort(q,j+1,r,k);
}
int main(){
int n,k;
vector<int> q(1000010,0);
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++){
scanf("%d",&q[i]);
}
int res = quick_sort(q,0,n-1,k);
printf("%d",res);
return 0;
}
题目要找的是第K小,您这样完全反了。。。