首页 > 代码库 > 最小的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 }
// 未完待续
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。