水王ID

题目：

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

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

一、设计思想

  1、先将其进行排序，由于水王出现的次数大于帖子数目的一半，所以在排序的中点处一定是水王，但是时间复杂度太高。

  2、消去不同的两项，由于水王发帖数大于帖子总数的一半，所以消到最后剩下的一定是水王。复杂度为n

二、源代码

#include<iostream.h>

int main()

{

    int n,m=1,water;

    int a[10]={3,4,2,2,5,5,6,2,2,2};

    water=a[0];

    for(n=1;n<10;n++)

	{

	   if(water!=a[n])

	   {

          m=m-1;

          if(m<=0)

		  {

            water=a[n+1];

            m=1;

            n++;

		  }

	   }

      else

	  {

		  water=a[n];

		  m=m+1;

       }

    }

    cout<<"waterman's id is："<<water<<endl;

    return 0;

}

三、实验截图

四、实验总结

找到解决办法之后，先考虑一下时间复杂度的问题，然后再想最优解。

代码优化和重要，所以我们一定要深入思考，一个程序是否完美，时间复杂度是占很大比重。