题目:Tango是微软亚洲研究院的一个试验项目。研究院的员工和实习生们都很喜欢在Tango上面交流灌水。传说,Tango有一大“水王”,他不但喜欢发贴,还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子(包括回帖)的列表,其中帖子作者的ID也在表中,你能快速找出这个传说中的Tango水王吗?
解法1:排序+遍历。O(nlogn)的时间复杂度。考虑到只需找到数量超过一半的ID,排序有点浪费,可以优化。
解法2:分治。将问题的规模逐渐缩小,直到找到答案,时间复杂度O(n)。算法:同时删去2个不同的ID,那么剩下的ID仍然符合"水王ID超过一半"的条件。
更直白一点,将水王的ID设为A集合,其他ID设为B集合(最坏情况是:每次分别从A、B集合抽取一个删除。因为可能从B中抽取2个删除),那么无论如何最后必然是A集合剩下,即为水王的ID。
int process(int *id,int n) { int count=0; int ans; for(int i=1;i<=n;i++) { if(!count) { ans=id[i]; count=1; } else { //对消2个不同的ID if(id[i]==ans) ans++; else ans--; } } return ans; }
扩展:若有3个发帖很多的ID,他们的发帖数目都超过了帖子总数目N的1/4,请找出他们。
算法:同上,分治。每次删除4个不同的ID!3个水王ID可用ans[0],ans[1],ans[2]记录。有不严谨的地方请指出。
void process(int *id,int n) { int count[4]; int ans[4]; memset(ans,-1,sizeof(ans)); for(int i=1;i<=n;i++) { int flag=0; for(int j=1;j<=3;j++) { if(ans[j]==id[i]) { count[j]++; flag=1; break; } } //跟3个ID不相同。 下面处理分2种情况:① ans[1-3]有空位②没空位,4个ID对消 if(!flag) { int empty=0; for(int j=1;j<=3;j++) { if(!count[j]) { ans[j]=id[i]; count[j]=1; empty=1; break; } } if(!empty) { for(int j=1;j<=3;j++) count[j]--; } } } }