资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

100万个数中找出最大的前K个数

   拿到这个题目我想到了很多方法,但是在我想到的方法中,要把在100万个数中找到前k个数,都不适用。最后通过我的不断研究,我想到了我认为最简单的方法,就是利用堆来做这道题目。

成都创新互联坚持“要么做到,要么别承诺”的工作理念,服务领域包括:网站设计制作、做网站、企业官网、英文网站、手机端网站、网站推广等服务,满足客户于互联网时代的石家庄网站设计、移动媒体设计的需求,帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴!

   下面我分析一下我用堆排序的思路:

     1.我先建一个大小为k的堆。

     2.把100万中前k个数放到这个堆中。

     3.把这个堆调成小堆。

     4.把100万个从k到100万之间的数字拿出来和堆的根结点作比较。

     5.如果根结点小于这之间的某一个数,就把这个数拿给根结点,然后继续调成小堆。否则继续找

     6.直到找完这100万个数,堆中放的就是最大的前k个数。

代码如下:

//下调
void _AdjustDown(int *arr, int parent, int size)
{
	int child = 2 * parent + 1;
	while (child arr[child + 1])
		{
			child++;//保证是孩子结点最大的一个节点
		}
		//交换
		if (arr[child] < arr[parent])
		{
			swap(arr[child], arr[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
int* Find(int *arr, int k,int N)
{
	assert(arr);
	assert(k > 0);
	int *str = new int[k];
	//把前k个元素放在堆中
	for (int i = 0; i < k; i++)
	{
		str[i] = arr[i];
	}
	//调成最小堆
	for (int j = (k - 2) / 2; j >= 0; j--)
	{
		_AdjustDown(str, j, k);
	}
	//然后k到N的所有数与堆中的根结点相比较
	for (int n = k; n < N; n++)
	{
		if (str[0] < arr[n])//如果根结点小于堆中k到N中的某一元素
		{
			str[0] = arr[n];//把这个元素赋值给根结点
			_AdjustDown(str, 0, k);//再一次调成最小堆
		}
	}
	return str;
	delete[]str;
}

  希望这个对你们有帮助。期待你们的回复,有什么不对的地方可以指出来啊。


标题名称:100万个数中找出最大的前K个数
分享地址:http://cdkjz.cn/article/gjpiig.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220