`
cozilla
  • 浏览: 91872 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

前k大个数

 
阅读更多
#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;
}

 

分享到:
评论

相关推荐

    寻找最大的K个数

    **核心思想**:通过二分查找的方式确定第K大的数,进而找到最大的K个数。 - **步骤**:首先设定一个范围[Vmin, Vmax],其中Vmin是最小值,Vmax是最大值。接着在这个范围内进行二分查找,找到使得不小于该值的数的...

    N个数求第K大

    c语言求N个数中第K大的值,采用改进型快排

    典型的Top K算法 找出一个数组里面前K个最大数.doc

    Top K算法是解决一个经典的问题,即在一个大规模的数组中找到前K个最大数的问题。在这个问题中,我们需要在一个数组中找到前K个最大数,例如在搜索引擎中,需要找出最热门的10个查询串。下面我们将详细地介绍Top K...

    求N个数中第K大的数

    基于快排的查找来得到N个数中第K大的数,时间复杂度为O(KlogN)

    分治法求第K大的数字

    利用分治法,解决对N个字中求第K大的数字的问题,效率比起逐个扫描有素提高

    在一堆数中取得前K个最大最小的数的方法

    - **求解不同的浮点数**:在面对需要找出N个数中最大的K个不同浮点数的问题时,上述方法同样适用,但需要注意浮点数的比较方式以及哈希键的设计方法。 - **求解第k到第m大的数**:可以将问题转化为求解m-k+1个第k...

    删数问题给定n 位正整数a,去掉其中任意k≤n 个数字后,剩下的数字按原次序排列组成一个

    对于给定的n位正整数a 和正整数k,设计一个算法找出剩下数字组成的新数 最小的删数方案。 «编程任务: 对于给定的正整数a,编程计算删去k个数字后得到的最小数。 Input 由文件input.txt提供输入数据。文件的第1...

    Python实现查找数组中任意第k大的数字算法示例

    在给定的示例中,介绍了一个利用分治思想实现的算法,类似于快速排序的partition过程,但目标是找到第k大的元素而非完全排序整个数组。 首先,我们需要理解什么是第k大的数字。在一组无序的数值中,第k大的数字是指...

    用递归法计算从n个正整数中选择k个数的不同组合数

    在计算机科学和数学中,计算从n个正整数中选择k个数的不同组合数是一项基本的任务,这涉及到组合数学中的组合(Combination)概念。组合是指从一个集合中不考虑顺序取出k个元素的方法数,它与排列(Permutation)...

    K尾相等数

    ### K尾相等数知识点解析 #### 一、概念理解 **K尾相等数**是一种特殊的数值计算问题,主要关注于某个整数k的幂次方运算后得到的结果的末几位数字是否出现周期性重复的现象。具体而言,对于一个整数k(k &gt; 0),...

    找第k小的数

    本文件给出了一种不同角度的在一个数组中找第k小的数,特别是在大型数据里有较快的速度(本算法给出的是20个数)。

    删数问题在(N个数字中,删除K个,使剩余的数字最小。)

    在N个数字中,删除K个,使剩余的数字最小。

    求有N个元素的数组中前k个最大的数?(N>=k)(python实现)

    由于只需要找出前k大的数,因此没必要对数组中所有的元素排序,可以采用部分排序的方式。具体思路为:第一次先遍历数组找到最大的数,第二次遍历从剩下的数组中找到最大的数(在整个数组中第二大的数)…共需遍历k次...

    用效率比较高的算法寻找K个最大的数

    用最优的算法,寻找到一个序列之中的K各最大的数

    17082 两个有序数序列中找第k小

    第一行有三个数 分别是长度m 长度n和k 中间空格相连(1&lt; m n&lt; 100000; 1&lt; k&lt; m+n) 第二行m个数分别是非减序的序列X 第三行n个数分别是非减序的序列Y 输出格式 序列X和Y的第k小的数 输入样例 ...

    微软技术面试-寻找最大的K个数

    ### 微软技术面试经典题目解析:寻找最大的K个数 #### 领域背景 在软件工程和技术面试领域,特别是在像微软这样的大型科技公司,面试官常常会提出一些算法和数据结构方面的问题来评估候选人的技术水平。这些面试题...

    java源代码n个数里找最大的k个

    Java源代码,n个数里找最大的k个,堆排序

    JAVA中寻找最大的K个数解法

    总结来说,寻找最大的K个数可以通过完全排序数组(如快速排序后取前K)或部分排序(如选择排序只找到前K个最大值)来实现。选择排序在某些情况下更有效,因为它不需要对整个数组进行排序,特别是当K远小于数组长度时...

    qiuwww#blog#GitBook-前k个最大的数1

    解题思路思路 1:局部淘汰法,只去关心存在的前 k 个,该方法与排序方法类似,用一个容器保存前 10000 个数,然后将剩余的所有数字——与容器内的最小数字相比

    两个有序数序列中找第k小(必做)

    已知两个已经排好序(非减序)的序列X和Y,其中X的长度为m,Y长度为n, 现在请你用分治算法,找出X和Y的第k小的数,算法时间复杂度为O(max{logm, logn})。

Global site tag (gtag.js) - Google Analytics