首页 > 其他 > 详细

课堂练习----找水王

时间:2015-04-21 22:17:18      阅读:273      评论:0      收藏:0      [点我收藏+]

题目要求:

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

  • 如果你有一张当前论坛的帖子(包括回帖)列表,其中帖子的作者的ID也在其中,你能快速的找到这个传说中的水王吗?
一、解决思路
       采用消除的方法,在遍历过程中,每次删除两个不同的ID,那么两两对消之后,由于该“水王”发帖数目超过了帖子数目的一半,所以剩下的水王ID仍然是超过一半,这样就可以通过重复这个过程把ID总数降低,到最后剩下的就是水王的ID,而且降低了时间复杂度为O(N)
二、程序代码
#include "stdafx.h"
#include<iostream.h>
#include "stdlib.h"
int curId=0; 
int count=0; 
void FindId(int arr[],int n) 
{ 
    for (int i=0;i<n;i++)   
    {   
        if (count==0)  
        {   
            count++;
            curId=arr[i];
        }   
        else  
        {   
            if(curId==arr[i]) 
                count++;   
            else         
                count--;  
        }   
    }   
}   
int main() 
{ 
    int n;  
    int * arr=new int[n]; 
    cout<<"请输入总的帖子数:"; 
    cin>>n; 
    cout<<"请输入每个水军的ID:"<<endl; 
    for(int i=0;i<n;i++) 
    { 
        cin>>arr[i]; 
    } 
    FindId(arr,n); 
    cout<<"水王的ID是:"<<curId<<endl;; 
    return 0;
} 

三、结果截图

技术分享

四、心得体会
     一开始想的就是利用选择和排序两种结合分析的,但是这样时间复杂度比较高,何况是拥有了“水王”发帖数目超过了帖子数目的一半这一前提,利用类似与游戏“开心消消乐”的方式进行消除,只不过是消除的是不相同的两个ID号,通过重复这个过程把ID总数降低,实现了把无数水军转化为较小规模的部分水军,把大问题变小化。
 

课堂练习----找水王

原文:http://www.cnblogs.com/luyu2783/p/4445314.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!