AcWing 786. 第k个数(JAVA)
原题链接
简单
作者:
hxzz
,
2021-01-11 13:19:26
,
所有人可见
,
阅读 254
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int k = cin.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; ++ i) {
a[i] = cin.nextInt();
}
System.out.println(quickSort(a, 0, n - 1, k - 1));
}
public static int quickSort(int[] a, int l, int r, int k) {
if (l >= r) return a[k];
int x = a[(l + r) >> 1];
int i = l - 1;
int j = r + 1;
while (i < j) {
do i ++ ; while(a[i] < x);
do j -- ; while(a[j] > x);
if (i < j) {
int temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
if (k <= j)
return quickSort(a, l, j, k);
else
return quickSort(a, j + 1, r, k);
}
}