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

接下来以第一个问题的形式来分析和编码,即 “求第 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(nlgn)
利用快速排序思想 O(n) 需要修改原始数据
利用最小堆思想 O(nlgk) 适用于海量数据

参考