AcWing 786. 第k个数Java
原题链接
简单
作者:
长街听风
,
2021-01-24 19:26:10
,
所有人可见
,
阅读 262
Java 代码
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(new BufferedInputStream(System.in));
int n = scanner.nextInt();
int k = scanner.nextInt();
int[] arr = new int[n];
for(int i = 0; i < n; i++){
arr[i] = scanner.nextInt();
}
int res = quickFind(arr,0,n-1,k);
System.out.println(res);
}
public static int quickFind(int[] arr,int l,int r,int k){
if(l >= r) return arr[l];//实际递归结束时,一定是l=r,即区间只有一个数了,这个数就是我们要找的第k个数
int base = arr[l];
int i = l-1, j = r + 1; //因为我们选择用do while 所以i,j的初始值不是l和r
while(i < j){
do{
i++;
}while(arr[i] < base);
do{
j--;
}while(arr[j] > base);
if(i < j){//交换结束后,两个指针都满足条件了,故应该往中间各移一位,所以上面用的do while
int temp =arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//排完一轮之后,我们根据左边的个数是否有k个来选择是递归左边还是右边
if(j - l + 1 >= k){//j-l+1即当前左边区间包含的数字个数
return quickFind(arr,l,j,k);
}else{
return quickFind(arr,j+1,r,k-(j-l+1));
}
}
}