首页 > 其他 > 详细

寻找发帖“水王”

时间:2014-03-30 09:08:54      阅读:471      评论:0      收藏:0      [点我收藏+]

寻找发帖“水王”

提出问题:
发帖“水王”指的是发帖数目超过了总帖数的一半。如果你有一个当前论坛上所有帖子(包括回帖)的列表,其中帖子作者的ID也在表中,你能快速找出这个发帖“水王”吗?

解法一:
大家最直接能想到的方法是:对所有的ID排序。然后再扫描一遍排好的ID列表,统计各个ID出现的次数。如果某个ID出现的次数超过总数的一半,那么就输出这个ID。

解法二:
对ID列表进行排序,如果一个ID出现的次数超过总数的一半。那么,无论“水王”的ID是什么,这个有序列表的中位数就一定会是这个ID。

解法三:
上面的两种解法都需要对ID列表进行排序,时间复杂度方面没有实质性的改进,能否避免排序呢???
如果每次删除两个不同的ID(不管是否包含水王的ID),那么,剩下的ID列表中,“水王”ID出现的次数仍然超过总数的一半。可以通过不断重复这个过程,把ID的数目降低(转换成更小的问题),从而得到答案。新的思路,避免了排序这个耗时的步骤,总的时间复杂度只有O(n)。
#include<cstdio>

using namespace std;

int main(int argc,char *argv[])
{
	int m,n;
	int i,j;
	int ans,count=0;
	scanf("%d%d",&m,&n);
	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
		{
			int temp;
			scanf("%d",&temp);
			if(count==0)
			{
				ans=temp;
				count=1;
			}
			else
			{
				if(ans==temp)
					count++;
				else
					count--;
			}
		}
	}
	printf("%d\n",ans);

	return 0;
}
解法四:
用C++ STL里面的map容器,直接统计每个ID出现的次数,然后扫描一遍map容器里的数据就可以了。。。
#include<cstdio>
#include<map>

using namespace std;

int main(int argc,char *argv[])
{
	int i,j;
	int m,n;
	map<int,int> v;
	scanf("%d%d",&m,&n);
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
		{
			int temp;
			scanf("%d",&temp);
			v[temp]++;
		}

	map<int,int>::iterator it;
	for(it=v.begin();it!=v.end();it++)
		if(it->second>m*n/2)
			break;
	printf("%d\n",it->first);

	return 0;
}


寻找发帖“水王”,布布扣,bubuko.com

寻找发帖“水王”

原文:http://blog.csdn.net/cstopcoder/article/details/22516031

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!