如果每次删除两个不同的ID（不管是否包含“水王”的ID），那么，在剩下的ID列表中，“水王”ID出现的次数仍然超过总数的一半。看到这一点之后，就可以通过不断重复这个过程，把ID列表中的ID总数降低（转化为更小的问题），从而得到问题的答案。新的思路，避免了排序这个耗时的步骤，总的时间复杂度只有O（N），且只需要常数的额外内存。伪代码如下：
[cpp]
Type Find(Type* ID, int N)
{
Type candidate;
int nTimes, i;
for(i = nTimes = 0; i < N; i++)
{
if(nTimes == 0)
{
candidate = ID[i], nTimes = 1;
}
else
{
if(candidate == ID[i])
nTimes++;
else
nTimes--;
}
}
return candidate;
}
扩展问题：统计结果表明，有3个发帖很多的ID，他们的发帖数目都超过了帖子总数目N的1/4。你能从发帖ID列表中快速找出他们的ID吗？
[cpp]
Type candidate1 ;
Type candidate2;
Type candidate3;
void Find(Type* ID, int N)
{
int nTimes1 = 0 ;
int nTimes2 = 0 ;
int nTimes3 = 0 ;
int i;
for( i = 0; i < N; i++)
{
if (nTimes1 == 0)
{
candidate1 = ID[i],nTimes1 = 1;
}
else
{
if (candidate1 == ID[i])
{
nTimes1++;
}
else
if (nTimes2 == 0)
{
candidate2 = ID[i],nTimes2 = 1;
}
else
{
if (candidate2 == ID[i])
{
}
else
{
if (nTimes3 == 0)
{
candidate3 = ID[i], nTimes3 = 1;
}
else
if (candidate3 == ID[i])
{
nTimes3++;
}
else
{
nTimes1--;
nTimes2--;
nTimes3--;
}
}
}
}
}
}
6、寻找最大的K个数
寻找N个数中最大的K个数，本质上就是寻找最大的K个数中最小的那个，也就是第K大的数。可以使用二分搜索的策略来寻找N个数中的第K大的数。对于一个给定的数p，可以在O（N）的时间复杂度内找出所有不小于p的数。
[cpp]
//寻找第k大的元素
int select(int a[],int n,int k)
{
if(n<=0||k>n||k<=0) return -1;
int left=0,right=n-1;
while(true)
{
int j=rand()%(right-left+1)+left;
swap(a,j,left);
j=partition(a,left,right);
if(k==j+1) return a[j];
else if(k
}
}
如果所有N个数都是正整数，且它们的取值范围不太大，可以考虑申请空间，记录每个整数出现的次数，然后再从大到小取最大的K个。比如，所有整数都在（0, MAXN）区间中的话，利用一个数组count[MAXN]来记录每个整数出现的个数（count[i]表示整数i在所有整数中出现的个数）。只需要扫描一遍就可以得到count数组。然后，寻找第K大的元素：
[cpp]
for(sumCount = 0, v = MAXN-1; v >= 0; v--)
{
sumCount += count[v];
if(sumCount >= K)
break;
}
return v;
极端情况下，如果N个整数各不相同，我们甚至只需要一个bit来存储这个整数是否存在。
7、快速寻找和等于一个给定的数字的两个数
解法一：穷举法，从数组中取出任意两个数字，计算两者之和是否为给定的数字。时间复杂度为O(N^2)
解法二：假设和为Sum，对于数组中每个数字arr[i]都判断Sum-arr[i]是否在数组中，就变成一个查找问题。提高查找效率，先排序，再用二分查找法等方法进行查找，查找的时间复杂度从O(N)降到O(logN)，总的时间复杂度为O(N*logN)。
更快的查找方法：hash表。给定的一个数字，根据hash映射查找另一个数字是否在数组中，只需O(1)的时间，这样总的时间复杂度降低到O(N)，但这需要额外的O(N)的hash表存储空间。
解法三：先对数组排序sort(a,n)，时间复杂度为O(N*logN),然后按下面的算法（O(N)的时间复杂度）查找，总的时间复杂度为O