在面试的时候碰到的问题，总结一下。这类问题有以下几种形式，但本质上是一样：

接下来以第一个问题的形式来分析和编码，即 “求第 k 个最大的数”

先排序…

这是我首先想到的，或者说想都没想就脱口而出的（。使用快速排序，时间复杂度为O(nlgn)。

而当使用选择排序是，时间复杂度为O(k*n)，伪代码如下：

1
2
3
4
5
6
7

for (int i = 0; i < k; i++) {
  int max = i;
  for (int j = i + 1; j < n; j++) {
    if (a[j] > a[max]) max = j;
  }
  exch(a, i, max);
}

n 为 数据的数量，k 为第k数

当lgn < k时，使用快速排序时间复杂度较小。但是其实我们做了很多无用功，题目只需要第 k 个最大的数，而我们则排序了整个数组。

利用快速排序原理

利用快速排序的partition()函数，**使得比第 k 个数大的都在数组左边。比第 k 个数小的都在右边，那么第 k 个数就是第 k 个最大的数。**使用二分法来查找第 k 个数的下标，所以时间复杂度为O(n)，因为是partition是原地的，所以需要修改原始数组。

 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

void exch(int *a, int i, int j) {
  int t = a[i];
  a[i] = a[j];
  a[j] = t;
}

int partition(int *a, int lo, int hi) {
  int povit = a[lo];
  int i = lo;
  for (int j = lo + 1; j <= hi;j++) {
    if (a[j] >= povit) {
      i++;
      exch(a, i, j);
    }
  }
  exch(a, i, lo);
  return i;
}

int k_th_max(int *a, int size, int k) {
  if (!a || k > size || k <= 0) return -1;
  int lo = 0, hi = size - 1;
  int p = partition(a, lo, hi);
  while (p != k - 1) {
    if (k - 1 < p) {
      hi = p - 1;
      p = partition(a, lo, hi);
    } else {
      lo = p + 1;
      p = partition(a, lo, hi);
    }
  }
  return a[k - 1];
}

使用递归的版本，参考《算法导论》第 9 章：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

int random_partition(int a[], int lo, int hi) {
  int x = rand() % (hi - lo + 1) + lo;
  exch(a, x, lo);
  return partition(a, lo, hi);
}

// recursive, T(n) = O(n);
int k_th_max1_1(int *a, int lo, int hi, int k) {
  if (lo == hi) return a[lo];
  int povit = random_partition(a, lo, hi);
  int p = povit - lo + 1;
  if (p == k) {
    return a[povit];
  } else if (p > k) {
    return k_th_max1_1(a, lo, povit - 1, k);
  } else {
    return k_th_max1_1(a, povit + 1, hi, k - p);
  }
}

关于时间复杂度的推导如下：

Best case:

$$T(n)=T({n \over 2}) + \Theta(n)$$

使用 master method：

$$n^{log_21}=n^0=1 < \Theta(n)$$

适用于 master method 的第三种情况，所以 $T(n) = \Theta(n)$

Worest case:

$$T(n)=T(n-1) + \Theta(n) = \Theta(n^2)$$

Except: $T(n)=\Theta(n)$

利用最小堆原理

用容量为 k 的最小堆来存储最大的 k 个数。最小堆堆顶的元素是最小的，扫描剩下的数据，如果比堆顶元素大，则替换之，然后调整堆。调整是时间复杂度为O(lgk),需要调整 n 次，所以总的时间复杂度也是O(nlgk)。

 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

void sink(int *heap, int i, int size) {
  while (2 * i <= size) {
    int j = 2 * i;  // select min child
    if (j < size && heap[j] > heap[j + 1]) j++;
    if (heap[i] <= heap[j]) break;  // not need to adjust
    exch(heap, i, j);
    i = j;
  }
}

void build_min_heap(int *heap, int size) {
  for (int i = size / 2; i >= 1; i--) {
    sink(heap, i, size);
  }
}

int k_th_max2(int *a, int size, int k) {
  int heap[k + 1];
  for (int i = 0; i < k; i++) {
    heap[i + 1] = a[i];
  }
  build_min_heap(heap, k);
  for (int i = k; i < size; i++) {
    if (a[i] > heap[1]) {
      heap[1] = a[i];
      sink(heap, 1, k);
    }
  }
  return heap[1];
}

同时，利用最小堆的这种方法十分适合海量数据的输入。假设题目要从一亿个数中找到第 k 大的数（k 远小于 一亿），由于内存的限制，我们不能够一次性将数据全部读入。而使用最小堆只需要读入 k 个元素，之后再依次读入剩下的元素，但不需要额外的空间。

总结

完整代码见GitHub。

方法 时间复杂度 备注
利用快速排序思想 O(n) 需要修改原始数据
利用最小堆思想 O(nlgk) 适用于海量数据
直接排序 O(nlgn)

参考