题目描述

给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列从小到大排序后的第k个数。

输入格式

第一行包含两个整数 n 和 k。

第二行包含 n 个整数（所有整数均在1~10^9范围内），表示整数数列。

输出格式

输出一个整数，表示数列的第k小数。

数据范围

1≤n≤100000
,
1≤k≤n

样例

输入样例：

5 3
2 4 1 5 3
输出样例：

3

(判断下标的方法)

• 下标判断方法:以快速排序为原型，每一次把区间分成两个部分，左区间的值都<=基准，右区间都值都>=基准
• 然后判断分界点跟k的大小，当分界点>=k时，说明要找的第k个数在左区间，反之在右区间，一直递归查询
• 当最后只剩一个元素的时候满足条件时，则该元素为第k个值
• 个数判断方法:或者每次区间划分之后判断左右区间的个数与k的大小

时间复杂度O(n)

参考文献

java 代码

//判断下标的方法
private static int quickSelect1(int[]a, int low, int high, int k){
//当最后只剩一个元素时，该元素就是第k个值
if(low>=high){
return a[high];
}
int privot=a[low];
int i=low-1,j=high+1;
while(i[HTML_REMOVED]privot);
if(i<j){
swap(a,i,j);
}
}
if(k<=j){
return quickSelect1(a,low,j,k);
}
else {
return quickSelect1(a, j + 1, high, k);
}
}

//判断个数的方法
public static int quickSelect2(int []a,int low,int high,int k){
if(low>=high){
return a[low];
}
int privot=a[low];
int i=low-1,j=high+1;
while (i[HTML_REMOVED]privot);
if(i[HTML_REMOVED]=k){
return quickSelect2(a,low,j,k);
}
else return quickSelect2(a,j+1,high,k-ll);
}