编程之美一书中寻找发帖“水王“的扩展问题描述如下：
统计结果表明，有3个发帖很多的ID，它们的发帖数码都超过了帖子总数目的N的1/4。你能从发帖ID列表中快速找出它们的ID吗？
参考书中”超级水王“的求解方案，我们每次删除4个不同的ID（不管是否包含题设中的3个ID），那么在剩下的ID列表中，题设中的3个ID各自出现的次数依旧超过总ID数的1/4，我们通过代码demo.cpp来找出题设中的3个ID:
#include <iostream> #include <vector> using namespace std; int main() { int inputNum,idValue[3],idCounts[3] = {0,0,0}; vector<int> intVec; cout << "Please input some intergers and enter ctrl+d to end input:" << endl; while(cin >> inputNum) intVec.push_back(inputNum); for(vector<int>::size_type index = 0; index != intVec.size(); index++) { if(idCounts[0] && idValue[0] == intVec[index]) { idCounts[0]++; } else if(idCounts[1] && idValue[1] == intVec[index]) { idCounts[1]++; } else if(idCounts[2] && idValue[2] == intVec[index]) { idCounts[2]++; } else if(0 == idCounts[0]) { idValue[0] = intVec[index]; idCounts[0]++; } else if(0 == idCounts[1]) { idValue[1] = intVec[index]; idCounts[1]++; } else if(0 == idCounts[2]) { idValue[2] = intVec[index]; idCounts[2]++; } else //与当前3个id都不相等，则从列表中删除这4个元素 { idCounts[0]--; idCounts[1]--; idCounts[2]--; } } cout << "the result is: " << idValue[0] << " " << idValue[1] << " " << idValue[2] << endl; return 0; }
在该程序中，数组idValue[3]用来存放题设中要求的3个ID的值，数组idCounts[3]用来存放当前情况下，idValue[3]中对应ID的个数，初始化均为为0。
在for循环中，首先判断当前处理的ID值是否与idValue[3]中某个元素相等，如果都不相等，那么就考虑下是否是由于idCounts[3]中某个元素不含ID导致的，如果数组idCounts[3]里的元素均大于0，那么这时刚好满足删除4个不同ID的条件，将idCounts[3]里的元素各自减一即可。最后剩下来的元素一定都是由题设要求的3个ID所组成的。
测试文件test.txt内容:
1 3 1 8 2 3 8 1 4 3 1 3 8 6 3 2 8 8 1 3 10 1 8
测试结果：
$ ./demo < test.txt $ the result is: 1 3 8
原文：http://www.cnblogs.com/bettercoder/p/3691965.html