Q: 某论坛有个水王，他发帖的数目超过了帖子总数的一半，如果你有这个论坛的所有帖子，且帖子作者ID也在表中，如何快速找到这个水王？
A:
解法一：
对所有的ID排序，扫描一遍排好序的ID列表，统计各ID的次数，超过一般的即是。
算法时间复杂度：O(NlogN+N) ，即排序加扫描时间。
解法二：
对ID排序，则第N/2项（从0开始编号）即是这个ID。
时间复杂度：O(NlogN+1)。
解法三：
思想：将大规模问题转化为等效的若干子问题，减小问题规模。
每次删除两个不同的ID，则剩下的ID列表中，水王的ID出现次数仍然超过一半。
时间复杂度：O(N)，只需要常数的额外内存。
TYPE find(TYPE *ID, int N)
{
TYPE candidate;
int nTimes, i;
for(i=nTimes=0; i
{
if(0==nTimes)
{
candidate = ID[i];
nTimes = 1;
}
else
{
if(candidate == ID[i])
nTimes++;
else
nTimes--;
}
}
return candidate;
}