AcWing 786. 第k个数
原题链接
简单
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt();
int[] d = new int[n];
for(int i = 0; i < n; i ++) d[i] = sc.nextInt();
int res = quick_sort(d, 0, n - 1, k - 1);
System.out.println(res);
}
public static int quick_sort(int[] d, int l, int r, int k){
if(l >= r) return d[l];
int i = l - 1, j = r + 1, x = d[l + r >> 1];
while(i < j){
do i ++; while(d[i] < x);
do j --; while(d[j] > x);
if(i < j){
int tmp = d[i];
d[i] = d[j];
d[j] = tmp;
}
}
//传参的时候为k
// int cnt = j - l + 1;
// if(k <= cnt) return quick_sort(d, l, j, k);
// else return quick_sort(d, j + 1, r, k - cnt);
//传参的时候为k-1
if(k <= j) return quick_sort(d, l, j, k);
else return quick_sort(d, j + 1, r, k);
}
}