AcWing 786. 第k个数
原题链接
简单
作者:
sowei
,
2021-05-19 10:37:27
,
所有人可见
,
阅读 194
import java.util.*;
class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] nums = new int[n];
for(int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
System.out.println(quick_select(nums, 0, n - 1, k));
}
static int quick_select(int[] nums, int l, int r, int k) {
if(l == r) return nums[l];
int i = l - 1, j = r + 1;
int tmp = 0;
int pivot = nums[l];
while(i < j) {
while(nums[++i] < pivot);
while(nums[--j] > pivot);
if(i < j) {
tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
int sl = j - l + 1;
if(k <= sl) return quick_select(nums, l, j, k);
else return quick_select(nums, j + 1, r, k - sl);
}
}