首页 > 代码库 > 【编程之美】2.5 寻找最大的k个数
【编程之美】2.5 寻找最大的k个数
有若干个互不相等的无序的数，怎么选出其中最大的k个数。
我自己的方案：因为学过找第k大数的O(N)算法，所以第一反应就是找第K大的数。然后把所有大于等于第k大的数取出来。
写这个知道算法的代码都花了2个多小时，反思，太慢了。 注意边界条件，不要混混沌沌的。
/************我自己的解法*****************///选择数组a[N]中最大的第k个数int Select(int * a, int N, int k){ if(k > N || a == NULL) { cout << "error!!!"; } if(N < 5) { qsort(a, N, sizeof(a[0]), cmp); return a[N - k]; } int arrNum = N/5; //可以整除5的数字 int surplus = N % 5; //除以5剩下的数字 int * mid = new int [arrNum]; //存储每一组的中位数 int * S1 = new int [N]; int * S2 = new int [N]; int posS1 = 0; int posS2 = 0; for(int i = 0; i < arrNum; i++) { qsort(a+i*5, 5, sizeof(a[0]), cmp); mid[i] = *(a + i * 5 + 3); } int midNum = Select(mid, arrNum, arrNum/2); for(int i = 0; i < arrNum; i++) { int * currentGroup = a + i * 5; if(currentGroup[2] < midNum) { memcpy(S1 + posS1, currentGroup, 3 * sizeof(a[0])); posS1 += 3; for(int j = 3; j < 5; j++) { if(currentGroup[j] <= midNum) S1[posS1++] = currentGroup[j]; else S2[posS2++] = currentGroup[j]; } } else { memcpy(S2 + posS2, currentGroup + 2, 2 * sizeof(a[0])); posS2 += 3; for(int j = 0; j < 2; j++) { if(currentGroup[j] <= midNum) S1[posS1++] = currentGroup[j]; else S2[posS2++] = currentGroup[j]; } } } for(int i = arrNum * 5; i < N; i++) { if(a[i] <= midNum) S1[posS1++] = a[i]; else S2[posS2++] = a[i]; } if(k == posS2) { return midNum; } else if(k < posS2) { return Select(S2, posS2, k); } else { return Select(S1, posS1, k - posS2); }}int * GetBiggestK(int * a, int N, int k){ int * biggestK = new int [k]; int numK = Select(a, N, k); int pos = 0; for(int i = 0; i < N; i++) { if(a[i]>=numK) { biggestK[pos++] = a[i]; } } return biggestK;}
编程之美对这种算法的评价是：由于这个线性算法的常数项比较大，在实际应用中有时效果并不好。
---------------------------------------------------------------------------------------------------------------------------
书上的解法：
解法一： 先排序，再取出最大的k个数 复杂度 O(NlogN)
解法二：类似于快速排序，先在数据中选一个数做标准，把数据划分为两个部分，大于等于选中数字S1个 和 小于选中数字S2个 。如果S1大于k则在S1个数中继续找最大的k个，如果S1小于k,则把这S1个数加入答案，并在S2中继续找其他的数字。 平均复杂度为O(NlogK).
/*********答案中 解法二*****************/int * GetBiggestKAns2(int * a, int N, int k){ if(a == NULL || k > N) { cout << "error!!!"<< endl; return NULL; } int first = a[0]; int head = 1; int tail = N - 1; int numAlready = 0; int postion = GetPosition(a, first, head, tail); swap(a[0], a[postion]); if(postion + 1 == k) { int * ans = new int [k]; memcpy(ans, a, k * sizeof(a[0])); return ans; } else if(postion + 1 > k) { return GetBiggestKAns2(a, postion + 1, k); } else { int * ans = new int [k]; memcpy(ans, a , (postion + 1) * sizeof(a[0])); int * ansPart = GetBiggestKAns2(a + postion + 1, N - postion - 1, k - postion - 1); memcpy(ans + postion + 1, ansPart, (k - postion - 1) * sizeof(a[0])); return ans; }}//交换时让大数在前，小数在后int GetPosition(int * a, int first, int p, int r){ int head = p; int tail = r; while(head < tail) { while(a[head] >= first) head++; while(a[tail] < first) tail--; if(head < tail) { swap(a[head], a[tail]); head++; tail--; } } return head - 1; //如果所有的数字都比first大 那么head会指向数组后的第一个数字 //如果所有的数字都比first小 那么head会指向第一个数字 都是恰好head - 1 是应该交换的位置}
【编程之美】2.5 寻找最大的k个数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。