0%

寻找前K大的数

找出N个整数里面前K大的整数

  • 思路1: 使用选择或冒泡算法,排出前K个元素,时间复杂度为O(N*K)
  • 思路2: 对这N个数排序,输出最大的K个,时间复杂度O(N*log(N))
  • 思路3: 快速排序的变种。前面寻找数组中第K大数的过程中,当找准数组中第K大数的位置时,数组中比K大的数据都在K的左边,比K小的数据都在K的右边。从而获取前K大的数据。其实也是部分排序。算法复杂度:O(N)
  • 思路4: 将前面K个元素构建为最小堆,将后面N - K个元素一次与堆顶比较,如果比堆顶元素大,则与堆顶交换,并将前面K个元素调整为最小堆,时间复杂度为O(N*log(K))

附最小堆实现代码

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
#include <algorithm>
#include <cstdio>
using namespace std;
// H是最小堆, heap_size是当前堆的大小
int H[10000], heap_size;
// 递归维护最小堆
void MIN_HEADPIFY(int i) {
int l = 2 * i, r = 2 * i + 1, largest = i;
if (l <= heap_size && H[l] < H[i]) {
largest = l;
}
if (r <= heap_size && H[r] < H[largest]) {
largest = r;
}
if (largest != i) {
swap(H[i], H[largest]);
MIN_HEADPIFY(largest);
}
}
int main() {
int n, k, tmp;
while (~scanf("%d%d", &n, &k)) {
heap_size = k;
for (int i = 0; i < k; i++) {
scanf("%d", &H[i + 1]);
}
// 对前k个数建最小堆
for (int i = k / 2; i >= 1; i--) {
MIN_HEADPIFY(i);
}
for (int i = 0; i < n - k; i++) {
scanf("%d", &tmp);
// 如果读入剩余的数比堆顶大, 则插入堆顶
// 并对堆顶进行维护
if (tmp > H[1]) {
H[1] = tmp;
MIN_HEADPIFY(1);
}
}
// 得到的H[1]---H[k]即为前k大数的集合
// 对其进行排序即可得到前k大的数
sort(H + 1, H + k + 1);
for (int i = k; i > 1; i--) {
printf("%d ", H[i]);
}
printf("%d\n", H[1]);
}
return 0;
}