微软编程之美--寻找发帖水王

条件：水王的发帖数目超过总帖子的数目的一半

普通解法是：排序，扫描统计整个列表来统计各个ID出现的次数，出现次数最多的为水王

特殊解法：如果每次删除两个不同的ID，那么剩下的ID列表里，水王的ID出现次数仍然超过一半

通过特殊解法原来的时间复杂度从o（N*logN+N）降到了o（N）且只需要常数的额外的内存

算法代码：

#include
using namespace std;
int main(){
        int n;
        cout<<"请输入n：";
        cin>>n;
        int *arr=new int[n];
        for(int i=0;i                 cout<<"请输入ID：";
                cin>>arr[i];       
        }
        int nTimes=0;
        int candidate;
        for(int i=0;i                 if(nTimes==0){
                        candidate=arr[i];
                        nTimes=1;
                }
                else {
                        if(candidate==arr[i]){
                                nTimes++;
                        }
                        else{
                                nTimes--;
                        }
                }
        }
        cout<<"出现次数最多的ID:"<         delete(arr);
        system("pause");
        return 0;
}