首页 > 代码库 > 算法：找出 n 个数中最小的 k 个数

算法：找出 n 个数中最小的 k 个数

2024-07-07 07:58:11   229人阅读

最简单的方法是将n个元素排序，取出最小的k个元素。这个算法的时间复杂度为 O(nlgn)。

然而在输入的n个元素互异的情况下，利用最大堆，我们可以获得时间复杂度为 O(nlgk)的算法。

 1 #include <stdio.h>
 2 
 3 #define N    128
 4 
 5 int heap[N], max_size, cur_pos = 1;
 6 
 7 void adjust(int i) { // bottom up
 8     int x = heap[i];
 9     int p = i / 2;
10     while (p != 0) {
11         if (x > heap[p]) { // max heap
12             heap[i] = heap[p];
13             i = p;
14             p = i / 2;
15         } else break;
16     }
17     heap[i] = x;
18 }
19 
20 void adjust2(int x) {  // top down
21     int i = 1, lim = max_size / 2;
22     if (x > heap[1]) return;
23     while (i <= lim) {
24         int L = i * 2, R = i * 2 + 1;
25         int tmp = heap[L], j = L;
26         if (R <= max_size && heap[R] > tmp) {
27             tmp = heap[R], j = R;
28         }
29         if (tmp > x) {
30             heap[i] = tmp, i = j; 
31         } else break;
32     }
33     heap[i] = x;
34 }
35 
36 void insert(int x) {
37     if (cur_pos <= max_size) {
38         heap[cur_pos] = x;
39         adjust(cur_pos);
40         cur_pos++; 
41     } else {
42         adjust2(x);
43     }
44 }
45 
46 void print() {
47     int i;
48     for (i = 1; i < cur_pos; i++) {
49         printf("%d ", heap[i]);
50     }
51     printf("\n");
52 }
53 
54 
55 int main() {
56     int data[10] = {1, 4, 2, 8, 5, 7, 9, 3, 0, 6};
57     int n = 10, k = 5;
58     int i;
59     
60     max_size = k;
61     for (i = 0; i < n; i++) {  
62         insert(data[i]); // O(lgk)
63         print();
64     } 
65     
66     return 0;
67 }

 


联系
我们