“找水王”问题续

题目：

1 三人行设计了一个灌水论坛。信息学院的学生都喜欢在上面交流灌水，传说在论坛上有一个“水王”，他不但喜欢发帖，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子数目的一半。

2 如果你有一张当前论坛的帖子（包括回帖）列表，其中帖子的作者的ID也在其中，你能快速的找到这个传说中的水王吗？(参考核心代码)

3 随着论坛的发展，管理员发现水王没有了，但是统计结果表明，有三个发帖很多的ID。据统计他们的发帖数量超过了1/4，你能从发帖列表中快速找到他们吗？

设计思想

此次试验有三个水王都超过了发帖总数的1/4,可将每个水王ID都与其它Id进行抵消最后剩下的就是三个水王，由于用户ID数量不可见,不知道哪个ID是水王，可以将前三个不同ID置为水王ID，将它们与当前三个ID都不同的ID都进行抵消,“水王”中抵消后数量剩余为0的即被淘汰,将当前最新的不同ID补充为水王继续抵消，由于四个水王一起进行抵消，而三个真正的水王数量超出了所有水贴ID的1/4，所以最后剩余的一定是三个水王ID

源代码

#include<iostream>
#include<assert.h>
using namespace std;
int * search(int *userId,int n)
{
	int curId[3]={0};//当前保存的三个不同ID
	int curNum[3]={0};//当前三个不同ID各自的数目;
	for(int i=0;i<n;i++)
	{
		if(curNum[0]==0&&userId[i]!=curId[1]&&userId[i]!=curId[2])//用户ID在当前ID中不存在相同ID且userID[0]的当前数量为0;
		{
			curNum[0]=1;
			curId[0]=userId[i];
		}
		else if(curNum[1]==0&&userId[i]!=curId[0]&&userId[i]!=curId[2])
		{
			curNum[1]=1;
			curId[1]=userId[i];
		}
		else if(curNum[2]==0&&userId[i]!=curId[0]&&userId[i]!=curId[1])
		{
			curNum[2]=1;
			curId[2]=userId[i];
		}
		else if(userId[i]==curId[0])//用户ID和当前ID相同则当前ID数+1
		{
			curNum[0]++;
		}
		else if(userId[i]==curId[1])
		{
			curNum[1]++;
		}
		else if(userId[i]==curId[2])
		{
			curNum[2]++;
		}
		else if(userId[i]!=curId[0]&&userId[i]!=curId[1]&&userId[i]!=curId[2])//四种ID一起抵消
		{
			curNum[0]--;
			curNum[1]--;
			curNum[2]--;
		}
	}
	return curId;//返回当前剩余的三个ID即为三个水王
}
void main()
{
	int n;
	int * userId;
	int curId[3]={0};
	int curNum[3]={0};
	int i;
	cout<<"输入灌水帖子数:";
	cin>>n;
	assert(n>0);
	userId=new int[n];
	cout<<"输入每一条灌水帖子id:"<<endl;
	for(i=0;i<n;i++)
	{
		cin>>userId[i];
	}
	for(i=0;i<3;i++)//输出三个水王ID
	{
		cout<<*(search(userId,n)+i)<<"\t";
	}
}

　　程序截图

实验总结

早先思路出现了错误,认为四个连续的用户ID抵消很难实现，时间复杂度会很大，后来实际操作才发现之前的思路只差一个转弯，只要将相同ID累加，不同于当前三个ID的四个一起抵消就可以了，固有的思维模式成了误区，造成了很大困扰；此程序虽然if语句用的有点多，但是却算不上复杂，略有收获，思维方式得到了拓宽

“找水王”问题续

推荐阅读