#include <cstdlib> #include <cstdio> #include <vector> #include <map> #include <algorithm> using namespace std; void qfind(vector<int>& a, int k, int left, int right, vector<int>&res ) { if (left > right || k <= 0) return; if (right - left + 1 <= k) { while (left <= right) res.push_back(a[left++]); return; } int pivot = a[left]; int i = left, j = right; while (i < j) { while (i < j && a[j] > pivot) j--; if (i < j) a[i++] = a[j]; while (i < j && a[i] <= pivot) i++; if (i < j) a[j--] = a[i]; } a[i] = pivot; qfind(a, k, left, i - 1 , res); if (k - (i-1-left + 1) > 0) res.push_back(a[i]); qfind(a, k-(i-left+1), i + 1, right, res); } vector<int> findKth(vector<int>& a, int k) { std::vector<int> res; qfind(a, k, 0, a.size() - 1, res); return res; } vector<int> findKth_heap(vector<int>& a, int k) { if (a.size() <= k) return a; vector<int> h(a.begin(), a.begin()+k); //auto cmp = (const int x, const int y){return x < y;}; // max heap make_heap(h.begin(), h.end()); for (int i = k; i < a.size(); i++) { if (a[i] < h[0]) { pop_heap(h.begin(), h.end()); h[k-1] = a[i]; push_heap(h.begin(), h.end()); } } return h; } void p(const vector<int>& a) { for (auto i = a.begin(); i != a.end(); i++) printf("%d ", *i); printf("\n"); } int main() { int a[] = {-1,1,1,1,1,1,1,1,11}; //int a[] = {9,8,7,6,45,5,4,3,4,2,1,1}; //int a[] = {1, 2,3,4 ,5 ,6, 7 ,8}; vector<int> v(a, a + sizeof(a) / sizeof(int)); auto res = findKth(v, 5); auto res2 = findKth_heap(v, 5); sort(res.begin(), res.end()); sort(res2.begin(), res2.end()); p(res); p(res2); return 0; }
相关推荐
c语言求N个数中第K大的值,采用改进型快排
寻找最大的K个数
基于快排的查找来得到N个数中第K大的数,时间复杂度为O(KlogN)
典型的Top K算法 找出一个数组里面前K个最大数.doc
利用分治法,解决对N个字中求第K大的数字的问题,效率比起逐个扫描有素提高
对于给定的n位正整数a 和正整数k,设计一个算法找出剩下数字组成的新数 最小的删数方案。 «编程任务: 对于给定的正整数a,编程计算删去k个数字后得到的最小数。 Input 由文件input.txt提供输入数据。文件的第1...
在一堆数中取出前K个最大最小的数的方法。这个是我们平时经常用到的排序问题,也是IT考试几乎必考的。多看看方法,还是有帮助的。
本文件给出了一种不同角度的在一个数组中找第k小的数,特别是在大型数据里有较快的速度(本算法给出的是20个数)。
在N个数字中,删除K个,使剩余的数字最小。
由于只需要找出前k大的数,因此没必要对数组中所有的元素排序,可以采用部分排序的方式。具体思路为:第一次先遍历数组找到最大的数,第二次遍历从剩下的数组中找到最大的数(在整个数组中第二大的数)…共需遍历k次...
用最优的算法,寻找到一个序列之中的K各最大的数
Java源代码,n个数里找最大的k个,堆排序
解题思路思路 1:局部淘汰法,只去关心存在的前 k 个,该方法与排序方法类似,用一个容器保存前 10000 个数,然后将剩余的所有数字——与容器内的最小数字相比
主要介绍了Python实现查找数组中任意第k大的数字算法,涉及Python针对数组的排序、查找等相关操作技巧,需要的朋友可以参考下
如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字,那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4,L = 2的时候(二位四进制数),K好数为11、13、20、22、30、31、33 共7个。...
已知两个已经排好序(非减序)的序列X和Y,其中X的长度为m,Y长度为n, 现在请你用分治算法,找出X和Y的第k小的数,算法时间复杂度为O(max{logm, logn})。
找出最大或最下的K个元素,可以使用Python库中的heapq模块,该模块提供两个函数nlargest()求最大K个和nsmallest()求最小K个。 下面我们举例说明: import heapq nums=[12,-9,-3,32,9,56,23,0,11,34] print(heapq....
分析:求解k个数的不同组合,我们可以用一维数组a[0]~a[k-1]来保存其中的一个结果,因为组合元 素是不重复的,可以约定其递增排列,因为数组中的元素是递增排列的: 所以a[k-1]即组合中的最后一个数,只能为k~n 令i=...
寻找最大的K个数,这个是面试中比较常见的一道题,网上也有很多例子,在这里是比较传统的解法