文档介绍：g1 g2
g1,g2 1 vector,
n g1
1 g2 -1 0
2,3,[[1,2],[2,4],[1,3],[4,3]],4
: 1
1
root
K
a, n K(K 1 n ) K
[1,3,5,2,2],5,3
2
49 24
1. ,
p
2. p - low + 1 == k a[p] k - 1
a[p] a[p] K
3. p - low + 1 > k k high = p - 1
1
4. p - low + 1 < k k low = p + 1, k =
k - (p - low + 1) 1.
“ ”
o(nlgn), o(n)
public class Finder {
publicblic int findKth(int[] a, int n, int K) {
return findKth(a, 0, n-1, K);
}
public int findKth(int[] a, int low, int high, int k) {
int part = partation(a, low, high);
if(k == part -low + 1) return a[part];
else if(k