首页 > 代码库 > 寻找水王

寻找水王

一、问题描述

  三人行设计了一个灌水论坛。信息学院的学生都喜欢在上面交流灌水,传说在论坛上有一个“水王”,他不但喜欢发帖,还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子数目的一半。

  如果你有一张当前论坛的帖子(包括回帖)列表,其中帖子的作者的ID也在其中,你能快速的找到这个传说中的水王吗?

二、设计思想

  因为水王的回帖数超过了一半,每次删除两个帖子的作者,删除条件是这两个作者不是同一个ID,最后剩下的肯定是水王。

三、代码实现

#include <iostream>
using namespace std;  
  
int find (int *a, int N)  
{  
    int candiate;  
    int i, time;  
    for (i = time = 0; i < N; i++)  
    {  
        if (0 == time)  
        {  
            candiate = a[i];  
            time = 1;  
        }  
        else  
        {  
            if (candiate == a[i])  
            {  
                time++;  
            }  
            else  
            {  
                time--;  
            }  
        }  
    }  
    return candiate;  
}   
  
  
void main()  
{  
    int a[] = {1,2,3,4,5,8,2,3,4,1,6,12};  
    cout<<"水王是:"<<find(a,12)<<endl;  
}  

寻找水王