数据结构与算法:大小根堆和快速排序 解决TopK问题

数据结构与算法:大小根堆和快速排序 解决TopK问题,第1张

问题:求出一组序列中值最小的前K个元素

在正常做法中,是先对这组元素排序,然后得出前k个元素,但排序算法的时间复杂度为O(n^2)或O(nlogn),问题就是 能不能在线性时间内找到top k的元素呢?

文章目录
  • 大小根堆
    • 求最小前k个元素
    • 代码示例
    • 求最大的前k个元素
    • 代码示例
    • 统计重复次数最少的k个元素
  • 快排分割求TopK

大小根堆 求最小前k个元素

给出一组元素,求最小的前三个元素。

需要用到一个大根堆,堆顶元素是最大的。
思想:把大根堆堆顶的大值不断淘汰,放入小值。

图示:

这里来看为什么统计最小值要用大根堆,首先拿前k(这里取3)个元素组成大根堆,然后继续向后遍历数组,11比堆顶小,那么堆顶元素出堆,将11添加进来,并重新调整为大顶堆;再往后遍历,6比堆顶小,堆顶元素出堆,将6添加进来,再次调整为大顶堆…
这个示例的后续元素都比堆顶元素大,所以遍历时不做处理了,最终结果已经得出。

但是有人会问,这个调整为大根堆,也会耗时啊,但实际上这个堆的元素只有k个,每次调整时,时间复杂度最坏为 O(logK),是一个常数级别的时间复杂度,再乘数组遍历的时间复杂度O(n),那么时间复杂度为 O(n * logK),logk为常数,可以省略,最终时间复杂度为 O(n)。

代码示例
#include 
#include 
#include 
#include 

using namespace std;

int main(void)
{
	vector<int> nums;
	srand(time(NULL));
	for (int i = 0; i < 1000; ++i)
	{
		nums.push_back(rand() % 10000 + 1);
	}

	// 求nums中值最小的前5个元素
	priority_queue<int> maxheap;
	int k = 5;

	// 前k个构建一个大根堆
	for (int i = 0; i < k; ++i)
	{
		maxheap.push(nums[i]);
	}

	// 遍历剩余元素
	for (int i = k; i < nums.size(); ++i)
	{
		if (maxheap.top() > nums[i])
		{
			maxheap.pop();
			maxheap.push(nums[i]);
		}
	}

	// 输出结果
	while (!maxheap.empty())
	{
		cout << maxheap.top() << " ";
		maxheap.pop();
	}
	cout << endl;

	return 0;
}

求最大的前k个元素

和上面相反,求最大元素,就应该使用小根堆,堆顶元素值最小。

思想:用k个元素构建小根堆,把堆顶小元素不断淘汰,把大元素放进来。

代码示例
#include 
#include 
#include 
#include 
using namespace std;

int main(void)
{
	vector<int> nums;
	srand(time(NULL));
	for (int i = 0; i < 1000; ++i)
	{
		nums.push_back(rand() % 10000 + 1);
	}

	// 求nums中值最大的前5个元素
	priority_queue<int> minheap;
	int k = 5;

	// 前k个构建一个大根堆
	for (int i = 0; i < k; ++i)
	{
		minheap.push(nums[i]);
	}

	// 遍历剩余元素
	for (int i = k; i < nums.size(); ++i)
	{
		if (minheap.top() < nums[i])
		{
			minheap.pop();
			minheap.push(nums[i]);
		}
	}
	// 输出结果
	while (!minheap.empty())
	{
		cout << minheap.top() << " ";
		minheap.pop();
	}
	cout << endl;

	return 0;
}

统计重复次数最少的k个元素

哈希表 + 大根堆

原理也很简单,先利用哈希表存储key-value,value为某元素出现次数,再利用大根堆,利用lambda表达式重写一个判断语句,最后遍历哈希表,找到结果。

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

int main(void)
{
	vector<int> nums;
	srand(time(NULL));
	for (int i = 0; i < 1000; ++i)
	{
		nums.push_back(rand() % 10000 + 1);
	}

	int k = 3;
	// 统计重复次数最小的前3个数字
	unordered_map<int, int> map;
	for (auto key : nums)
	{
		map[key]++;
	}

	// 放入大根堆时,需要放key-value键值对
	using Type = pair<int, int>;
	using Cmp = function<bool(Type&, Type&)>;
	priority_queue<Type, vector<Type>, Cmp> maxheap(
		[](Type& a, Type& b)->bool {
			return a.second < b.second;
		}
	);

	auto it = map.begin();
	for (int i = 0; i < k; ++i, ++it)
	{
		maxheap.push(*it);
	}

	for (; it != map.end(); ++it)
	{
		if (maxheap.top().second > it->second)
		{
			maxheap.pop();
			maxheap.push(*it);
		}
	}

	while (!maxheap.empty())
	{
		cout << "key: " << maxheap.top().first
			<< " cnt: " << maxheap.top().second << endl;
		maxheap.pop();
	}

	return 0;
}

那么,统计重复次数最大的k个元素,和上面思想一样,使用哈希表 + 小根堆。

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

int main(void)
{
	vector<int> nums;
	srand(time(NULL));
	for (int i = 0; i < 1000; ++i)
	{
		nums.push_back(rand() % 1000 + 1);
	}

	// 统计重复次数最大的前3个数字
	int k = 3;
	unordered_map<int, int> map;
	for (auto key : nums)
	{
		map[key]++;
	}

	// 放入大根堆时,需要放key-value键值对
	using Type = pair<int, int>;
	using Cmp = function<bool(Type&, Type&)>;
	priority_queue<Type, vector<Type>, Cmp> minheap(
		[](Type& a, Type& b)->bool {
			return a.second > b.second;
		}
	);

	auto it = map.begin();
	for (int i = 0; i < k; ++i, ++it)
	{
		minheap.push(*it);
	}

	for (; it != map.end(); ++it)
	{
		if (minheap.top().second < it->second)
		{
			minheap.pop();
			minheap.push(*it);
		}
	}

	while (!minheap.empty())
	{
		cout << "key: " << minheap.top().first
			<< " cnt: " << minheap.top().second << endl;
		minheap.pop();
	}
	return 0;
}

快排分割求TopK

如果对快速排序了解较少,可以看这一篇文章:【点此查看】

原理就是利用快速排序的划分函数Partition,该函数每次分割完,在基准值左边的元素,都是比基准值小的,右边全是比基准值大的元素,利用基准值的位置和k进行比较,很方便得到TopK元素。

#include 
#include 

using namespace std;

// 分割函数
int Partition(int* nums, int left, int right)
{
	int key = nums[left];

	while (left < right)
	{
		while (left < right && nums[right] > key)
			right--;

		if (left < right)
		{
			nums[left] = nums[right];
			left++;
		}

		while (left < right && nums[left] < key)
			left++;
		
		if (left < right)
		{
			nums[right] = nums[left];
			right--;
		}
	}

	nums[left] = key;
	return left;
}

// 求Topk函数
void selectTopK(int* nums, int left, int right, int k)
{
	int pos = Partition(nums, left, right);
	if (pos == k - 1)
	{
		return;
	}
	else if (pos > k - 1)
	{
		selectTopK(nums, left, pos - 1, k);
	}
	else
	{
		selectTopK(nums, pos + 1, right, k);
	}
}

void Show(int* nums, int size)
{
	for (int i = 0; i < size; ++i)
	{
		cout << nums[i] << " ";
	}
	cout << endl;
}

int main(void)
{
	int nums[] = { 64, 45, 52, 80, 66, 68, 0, 2, 18, 75 };
	int size = sizeof(nums) / sizeof(nums[0]);
	Show(nums, size);

	// 求值最小的前三个元素
	int k = 3;
	selectTopK(nums, 0, size - 1, k);
	Show(nums, k);
	return 0;
}

欢迎分享,转载请注明来源:内存溢出

原文地址:https://outofmemory.cn/langs/3002968.html

(0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
上一篇 2022-09-27
下一篇2022-09-27

随机推荐

  • 谜语人是什么意思

    谜语人,网络流行语,指本来一两句话就能讲明白的事情,非要在其中插进一大堆意义不明对剧情根本没有一点用处的话,就像讲谜语一样。。也指说话故弄玄虚,半、天放不出屁来的人。谜语人滚出哥谭! 关于谜语人,举个

  • 你这是在为难我胖虎是什么意思

    为难我胖虎,如字面意思,你不要为难我啊,就是当某些不想做的事情落在头上时可使用的句子。为难我胖虎出处:来源:《哆啦A梦》表情包出自一张表情包,图中胖虎一脸凶神恶煞,并配词“我看,你就是刁难我胖虎”,胖

  • 网络语WDM是什么意思

    wdm, 饭圈用语,我的妈的意思。wdm,表示震惊,感叹例如:wdm 真的有这样的好事!!网络语WDM是什么意思wdm, 饭圈用语,我的妈的意思。wdm,表示震惊,感叹例如:wdm 真的有这样的好事

    2022-12-06
    000
  • 网络语铲屎官是什么意思

    铲屎官,网络流行语,意指给猫、狗铲屎的人类。爱猫爱狗人士将自己比作铲屎官,以表诙谐幽默气氛。多数用来指养猫、养狗者。汪星人与喵星人每次便便完后,只能由人来为其清理便便,久而久之,人就变成铲屎官喽。这是

    2022-12-06
    000
  • 神龛是什么意思

    神龛,顾名思义,就是古时候民间用来供奉神像或者是祖宗牌位的阁子。神龛有大有小,一般常见于祠堂之中,是由木头雕刻而成的。古时候的大户人家家里会有专门用来供奉祖先牌位的祠堂,而祠堂里都放置雕刻精美的神龛

    2022-12-06
    000
  • 正史三国谋士真实排行榜

    三国谋士正史上没有进行评比,正史中杰出的谋士有荀彧、郭嘉、孔明、庞统、鲁肃周瑜、陆逊、贾诩、程昱、田丰,荀彧是曹魏第一谋臣,不仅谋略过人,而且政略出众,是一个

    2022-12-06
    000
  • 馆陶为什么恨窦漪房

    历史上,馆陶是窦漪房的女儿,窦漪房视馆陶如掌上明珠般,馆陶从小被窦漪房呵护着长大,性格娇蛮任性。而且很天真,很容易就听信了别的的馋言。馆陶事事与母亲对着干,馆

    2022-12-06
    000
  • 诸葛瑾的一生是怎样的

    诸葛瑾,字子瑜,三国时期吴国重臣。他为人胸怀宽广,温厚诚信,深得孙权的信赖。诸葛瑾年轻时博览群书,后来因中原战乱而避乱江东。在孙权的姊婿曲阿弘咨的推荐下,孙权任命诸葛瑾为中司马。公元219年,诸葛瑾跟

    2022-12-06
    000
  • 黄巾起义领导者是谁

    黄巾起义领导者是张角,这场农民战争发生在东汉末年汉灵帝时期,当时东汉政权被宦官和外戚所掌控,朝廷迂腐不堪,争斗不断,不仅国力日渐衰弱,百姓的日子也是苦不堪言,这时候巨鹿人张角发动了黄巾起义,贫苦农民

    2022-12-06
    000

发表评论

登录后才能评论

评论列表(0条)

    保存