当k=Sl时,为什么要去左侧递归
假设第k小的数字为K
原理1:这是因为,K的定义为第k小的数字,这代表着,如果数组内没有重复数字的情况下,在整个数组中小于等于K的数字一共有且仅有有k个。
原理2:根据快排的论证可得,按照视频中的方法进行递归之后,[0,Sl]中的所有数字都小于等于k。
这意味着,第k小的数字必然在[0,Sl]中,而不可能在另一侧,如果它在另一侧,那么在整个数组中小于等于K的数字就存在了k+1个,与其本身的定义相冲突。
故而应当在[0,Sl]中递归,而非是另一侧
代码
import java.io.*;
import java.util.Arrays;
public class Main {
private static int[] ints;
private static int k;
private static int n;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String nk = reader.readLine();
String[] nks = nk.split("\\s+");
n = Integer.parseInt(nks[0]);
k = Integer.parseInt(nks[1]);
ints = new int[n];
String nums = reader.readLine();
String[] strings = nums.split("\\s+");
for (int i = 0; i < n; i++) {
ints[i] = Integer.parseInt(strings[i]);
}
System.out.println(core(0, n - 1));
}
private static int core(int L, int R) {
if (L == R) return ints[L];
int mid = L + R >> 1;
int l = L - 1;
int r = R + 1;
int x = ints[mid];
while (l < r) {
do l++; while (ints[l] < x);
do r--; while (ints[r] > x);
if (l < r) swap(l, r);
}
// ints[L,l - 1] <= x, ints[r + 1, R] >= x
// l >= r, r \in [L,R - 1], l \in [L, R]
// ints[L, r] <= x,ints[r + 1, R] >= x
if (r + 1 < k) return core(r + 1, R);
else return core(L, r);
}
private static void swap(int l, int r) {
int temp = ints[l];
ints[l] = ints[r];
ints[r] = temp;
}
}