找水王

一、题目及题目要求

题目:

        三人行设计了一个灌水论坛。信息学院的学生都喜欢在上面交流灌水,传说在论坛上有一个“水王”,他不但喜欢发帖,还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子数目的一半。 如果你有一张当前论坛的帖子(包括回帖)列表,其中帖子的作者的ID也在其中,你能快速的找到这个传说中的水王吗?

二、设计思路:

      看见这个题目,刚开始自己的思路就是排序,什么折半排序冒泡排序的,但是都太过繁琐,复杂度也较高,之后根据老师上课给的提示“相减”,然后有了以下的一些新的思路。

       由于水贴王发帖过半,所以,将帖子列表从第一个ID开始,两两相邻比较,然后将ID不同的消除,最后剩下的一定是水贴王的ID。

       因为帖子肯定有一个总的序号的表统计着,所以先把这个表保存为一个数组

1、把帖子列表,抽象为一个一维数组arr[NUM],输入长度length为id总数,每个数组元素为一个id。

2、再设置一个循环,按照顺序来依次两两比较,如果作者id相同则保留,如果作者id不同则消除。

3、最后剩下id即为水王id

三、源程序:

#include<iostream>
using namespace std;
#define NUM 100
 int find(int arr[], int n)//找出水王的函数
 {
     int shuiwang;
     int findshuiwang = 0; 
     int count=0;  //标记
     for(int i=0;i<n;i++)
     { 
         if(count == 0)//初始时,把数组第一个元素赋给shuiwang
         { 
             shuiwang = arr[i]; 
             count = 1; 
         } 
         else
         { 
             if(shuiwang == arr[i]) //相等的时候互相不消除
                 count ++; 
             else //不等的时候互相消除
                 count --; 
         } 
    }
         return shuiwang;
    }

int main()
{
      int length=0;//先定义一个数组的长度
      cout<<"请输入n的值"<<endl;
      cin>>length;
      int arr[NUM];
      cout<<"请输入id(不为0):"<<endl;
      for(int i=0;i<=(length-1);i++)
       {
           cin>>arr[i];
       }
       int ID=find(arr,length);
        cout<<"水军的ID是"<<ID<<endl;
        return 0;
}

四、运行截图

五、项目计划日志      

日期&&任务

听课 编写程序 阅读相关书籍 网上查找资料   日总计
周一 100   30 30 160
周二     30 30 60
周三   30 30 10 70
周四 100 20  30   150
周五   120   30 30 180
周六          
周日          
周总计 200 170 150 100

620

时间记录日志

5/16

日期 开始时间 结束时间 中断时间 净时间 活动 备注
5/16 14:00 15:50 10 100 听课 软件工程上课
  21:04 21:  34 0 30 阅读书籍 《梦断代码》
  22:10 22: 40 30 网上查找资料  
 5/17  18:00  18:30  0  30  阅读书籍 《梦断代码》 
  22:  15 22:  45 30 网上查找资料  
5/18 19:  25 20: 00 5 30 编写程序 找水王
  22:00 22: 30 0 30 阅读书籍 《梦断代码》
  22:40 22: 50 0 10 查找资料  
5/19 14:00 15:  50 10 100 上课 软件工程上机
  18:26 18: 50 20 编写程序 找水王
   22:00  22:30  0  30  阅读书籍  《梦断代码》
5/20 14:  00 16:  20 20 120  编写程序 找水王
  11:23 12: 00 7 30 网上查找资料  
   21:00  21:30  0  30  阅读书籍  《构建之法》

六、个人总结

      对于这个题目,一开始的思路,我想也是多数同学会有的思路,就是排序嘛,大不了就一个一个的找然后再逐个累加算出他们的ID号出现的总数,但是这个方法无论是在复杂度还有许多方面都不够简便,然后在老师的提示下“相减”,然后有了新的思。后来老师提到了遍历然后排序,中间项肯定是水王ID,可是时间复杂度为n*n,为了降低时间复杂度,老师提示用两两消除的思想,后来我们就想到了如何解决。由此可见,我们的思路还不是很开阔,只局限于那些 自己学过的简单的常用的知识,所以我还有很大的进步的空间。

原文地址:https://www.cnblogs.com/qizhonh/p/5512905.html