题目描述
第k个数[利用快排]–> 完成”快速选择”
思想
当k在左半边, 答案肯定在左半边中,则迭代左半边,
反之亦然.
时间复杂度
nlogn/2
java 代码
import java.io.*;
import java.util.*;
class Main{
static int[] q;
static int k;
public static void main(String args[]) throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
//读行. 用 "空格" 分割
int [] s = Arrays.asList(in.readLine().split(" ")).stream().mapToInt(Integer::parseInt).toArray();
//对每个字串转成 int
//数组长度
int n = s[0];
//第k个数字
k = s[1];
//读取整行转为int 数组
q = Arrays.asList(in.readLine().split(" ")).stream().mapToInt(Integer::parseInt).toArray();
//传入左右边界+ 第k个数字;
int a = quick_select(0,n-1,k);
System.out.print(q[a]);
}
static int quick_select(int l, int r, int k){
if(l>=r) return l;
int i = l - 1, j = r + 1;
int x = q[l+r>>1];
while(i<j){
do i++; while(q[i] < x);
do j--; while(q[j] > x);
if(i<j){
int temp = q[i];
q[i] = q[j];
q[j] = temp;
}
}
// k 如果在左半边, 则k 不变,
// 如果k 在右半边, 则左半边的长度不会执行.长度则减了整个左半边.
// 所以k 也需要 减去左半边长度.
int sl = j-l+1;
if(k <= sl){
return quick_select(l, j, k);
}else{
return quick_select(j+1, r, k-sl);
}
}
}