基本思路

利用快排中的partition算法对数组a[n]进行划分成：a[0..p-1], a[p], a[p+1..n-1], 如果p+1=k，完成；如果p+1>k, 问题转化为在a[0..p-1]中查找topk；否则，问题转化为在a[p+1..n-1]中查找top(k-p-1)。这样，我们利用减治的思路一步步对数组做原地划分，算法终止时，我们直接取数组的前k个元素即可

实现

topK

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
 * 查找数组的top K元素
 * @param {Array} arr
 * @param {Number} k
 */
function topK(arr, k) {
  topKRange(arr, 0, arr.length - 1, k);
  return arr.slice(0, k);
}

/**
 * 在arr[l..h]中查找top k
 * @param {Array} arr 
 * @param {Number} l 
 * @param {Number} h 
 * @param {Number} k 
 */
function topKRange(arr, l, h, k) {
  if (l >= h) return;

  const m = partition(arr, l, h);

  if (m - l + 1 === k) {
    return;
  }

  if (m - l + 1 > k) {
    topKRange(arr, l, m - 1, k);
  } else {
    topKRange(arr, m + 1, h, k - (m - l + 1));
  }
}

/**
 * partition arr by the last element
 * @param {Array} arr 
 * @param {Number} l 
 * @param {Number} h 
 * @returns index of the partition element
 */
function partition(arr, l, h) {
  let i = l;
  let j = l;

  while (j < h) {
    if (arr[j] > arr[h]) {
      swapArrEle(arr, i++, j++);
    } else {
      j++;
    }
  }

  swapArrEle(arr, i, h);
  return i;
}

function swapArrEle(arr, i, j) {
  if (i === j) return;

  const tmp = arr[j];
  arr[j] = arr[i];
  arr[i] = tmp;
}