首页 > 代码库 > 最小的K个数

最小的K个数

从有N个数的数组中需找最小的K个数。

方法一:O(nlog(n))

排序后的前K个数。

方法二:O(n)

1. 需要2k个额外的临时变量。

 1 #include <iostream> 2 #include <limits> 3  4 using namespace std; 5  6 const int len = 1000; 7 int n = 0, k = 0; 8  9 int arr[len];10 int minA[len], pos[len];                    // 保存前k个最小值和最小值的下标11 12 void moveMinA(int k);                        // 插入一个最小值,将之前的最小值向后赋值 13 void selectNK(int arr[], int n, int k);14 15 int main()16 {17     cout << "please input n, k, array:\n";18     cin >> n >> k;19     for (int i = 0; i < n; ++ i)20         cin >> arr[i];21 22     for (int i = 0; i < len; ++ i) 23         minA[i] = numeric_limits<int>::max();24 25     selectNK(arr, n, k);26 27     return 0;28 }29 30 void selectNK(int arr[], int n, int k)31 {32     for (int i = 0; i < n; ++ i) {33         for (int j = 0; j < k; ++ j) {34             if (arr[i] < minA[j]) {35                 moveMinA(j);36                 pos[j] = i; minA[j] = arr[i];37                 break;38             }39         }40     }41     for (int i = 0; i < k; ++ i) {42         cout << "min" << i << " = " << minA[i] << \t;43     }44 }45 46 void moveMinA(int j)47 {48     if (j != k - 1) {49         for (int i = k - 1; i > j; -- i) {50             pos[i] = pos[i - 1];51             minA[i] = minA[i - 1];52         }53     }54 }

// 未完待续