寻找小水王
“超级水王”没有了。有3个发帖很多的ID,他们的 数目都超过了 总数目N的1/4。你能从 ID列表中快速找出他们的ID吗?
一.设计思路
上题只需要一个结果,而现在需要3个结果,所以考虑数组作为返回值,同时,上题用到的nTimes,也应改为一个大小为3的数组。如何保证最终返回的数组的3个元素就是3个灌水最多的用户呢?首先分析其所占比例,各超过1/4,也就是说剩下的其它ID所占帖数就不足总帖数1/4了。现在我们需要3个变量来记录当前遍历过的3个不同的ID,而nTimes的3个元素分别对应当前遍历过的3个ID出现的个数。如果遍历中有某个ID不同于这3个当前ID,我们就判断当前3个ID是否有某个的nTimes为0,如果有,那这个新遍历的ID就取而代之,并赋1为它的遍历数(即nTimes减1),如果当前3个ID的nTimes皆不为0,则3个ID的nTimes皆减去1,这也就是解决本文题的关键了。由于非水王ID不满总帖数的1/4,与上题思路相同,所遍历ID与当前3个ID不同时,就一同抵消(即3个当前ID的nTimes值减1),最终留下来的3个当前ID总会是3个超过1/4的水王ID。
二.代码实现
//寻找小水王 //孔宇航 2016/5/23 #include <iostream> using namespace std; void intID(int length,int Arr[]) { cout<<"输入发帖人的ID:"<<endl; for(int i=0;i<length;i++) { cin>>Arr[i]; } } int main() { int length;//发帖人ID的个数 int time[3]={0,0,0}; //记录次数的数组 int ID[3]={-1,-1,-1}; //3个小水王数组 cout<<"请输入帖子数量:"; cin>>length; int * wk=new int [length]; intID(length,wk); for(int i=0;i<length;i++) { if(time[0]==0 && wk[i]!=ID[1] && wk[i]!=ID[2]) //初始设置 { time[0]=1; ID[0]=wk[i]; } else if(time[1]==0 && wk[i]!=ID[0] && wk[i]!=ID[2]) { time[1]=1; ID[1]=wk[i]; } else if(time[2]==0 && wk[i]!=ID[0] && wk[i]!=ID[1]) { time[2]=1; ID[2]=wk[i]; } else if(wk[i]!=ID[0] && wk[i]!=ID[1] && wk[i]!=ID[2])//不同次数减 { time[0]--; time[1]--; time[2]--; } else if(wk[i]==ID[0])//相同次数加 { time[0]++; } else if(wk[i]==ID[1]) { time[1]++; } else if(wk[i]==ID[2]) { time[2]++; } } cout<<"小水王的ID为:"<<ID[0]<<" "<<ID[1]<<" "<<ID[2]<<endl; return 0; }
三.运行结果
四.实验总结
此次实验在上一次的基础上又有了新的改进,看似不同其实道理是一样的,只是计数由原来的一个数变成了数组。试着想过别的算法没有结果,只能延续上一次的思路,编程过程中还算顺利,出现的错误越来越少了,希望继续保持这样O(∩_∩)O。