编程之美第2.3题————寻找发帖“水王”
题目描述：
Tango是微软亚洲研究院的一个试验项目。研究院的员工和实习生们都很喜欢在Tango上面交流灌水。传说，Tango有一大“水王”，他不但喜欢发贴，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子（包括回帖）的列表，其中帖子作者的ID也在表中，你能快速找出这个传说中的Tango水王吗？
首先，我们可以假设有这样一个数据结构来表示帖子
[cpp]
type struct post
{
char* title;
char* content;
int uid;
}post_t;
[/cpp]
题目告诉我们已知所有帖子的列表，也就是说我们知道了所有帖子的链表 post_t* post_list，或者是所有帖子的数组post_array[num]。然后让我们找到出现次数最多的uid是多少，并且该uid一定超过了总和的一半。为了叙述方便，下面用数组举例。最容易就想到的方法，就是遍历整个数组，记录每一个uid出现的次数，然后再比较一下，求出最大的。
其实，这个问题就可以等价于：求数组中出现次数大于一半的那个数
解法一
对数组排序，然后遍历排好序的数组，统计各ID出现的次数，找到超过一半的那个即可。代码如下：
[cpp]
int Find (int* post, int len)
{
sort(post, post + len);
int num = 1;
for(int i = 0; i < len; i++)
{
if(post[i] == post[i + 1])
num++;
else
num = 1;
if(num > len / 2)
return post[i];
}
return 0;
}
[/cpp]
这里先调用了一下sort函数排序，也可以换成自己的排序函数。
因为采用了排序，复杂度有所提升，于是书中提出了第二种解法，我觉得是比较巧妙的。
解法二
由于x出现的次数大于总数的一半，所以如果每次删除两个不同的值，不管是否有x，在剩下的数中，x的次数依然会大于总数的一半。
于是，算法可以这样设计
[cpp]
int Find2 (int* post, int len)
{
int x;
int times = 0;
for(int i = 0; i < len; i++)
{
if(times == 0)
{
x = post[i];
times = 1;
}
else
{
if(x == post[i])
times++;
else
times–;
}
}
return x;
}
[/cpp]
该算法不用排序，很巧妙的通过向前移动达到了“删除”的目的，自己真的没想到：）。
越来越觉得优美的代码就是美了，简洁明了，而又功能强大。
扩展问题：
随着Tango的发展，管理员发现，“超级水王”没有了。统计结果表明，有3个发帖很多的ID，他们的发帖数目都超过了帖子总数目N的1/4。你能从发帖ID列表中快速找出他们的ID吗？
解法x
这个思路就是一样的了，设a，b，c三人的发帖数都超过了 1/4，那么把4个不同id删除以后，并不影响剩余数组中a，b，c三人的发帖数都超过1/4这个结果。示意图如下所示。
把数组分为四个四个数字一组的来看。由于a的发帖数超过了1/4，所以，平均下来，在每一个分组里都有一个a，并且至少在某一组中有大于一个的a，假如分组1中的四个数字都不相同，我们删除分组1，如果a不在分组1里面，那么在剩余的2~n组中，a出现的次数显然会继续大于1/4；如果a在分组1里面，那么在剩余2~n组中，平均下来，a还是会至少在每一个分组出现一次。所以只要分组1中4个数字不相同（主要是保证没有两个a），那么删除分组1，并不改变a在剩余数组中出现次数依然大于1/4的事实。同理b，c。
代码如下：
[cpp]
void Findx(int* post, int len)
{
int a, b, c;
int ta = 0;
int tb = 0;
int tc = 0;
for(int i = 0; i < len; i++)
{
if(ta == 0)
{
a = post[i];
ta++;
}
else if(a == post[i])
ta++;
else if(tb == 0)
{
b = post[i];
tb++;
}
else if(b == post[i])
tb++;
else if(tc == 0)
{
c = post[i];
tc++;
}
else if(c == post[i])
tc++;
else
{
ta–;
tb–;
tc–;
}
}
cout << "a: " << a << "\t";
cout << "b: " << b << "\t";
cout << "c: " << c << "\t";
}
[/cpp]
Enjoy!