深圳市住房城乡建设局网站首页谷歌外贸平台推广需要多少钱

1.题目。

    三人行设计了一个灌水论坛。信息学院的学生都喜欢在上面交流灌水，传说在论坛上有一个“水王”，

他不但喜欢发帖，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子数目的一半。

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

 

 2.设计思想。

因为“水王”发表的帖子超过一半，所以任意消除两两不同的ID号，则剩下的ID号一定为“水王”ID号。通过消除的方法实现时间复杂度为n，将第一个ID号压入栈中，与第二个ID号比较，不一样则弹出栈，表示消除这两个ID号，再将第三个ID号压入栈；否则将第二个ID号压入栈。以此类推，一直到最后一个ID号，则栈中剩下的则为“水王”ID号。

 3.代码。

 

#include<iostream.h>
#include<stdlib.h> 
#define MAXSIZE 100typedef struct
{int *base;int *top;int stacksize;
}SqStack;int InitStack(SqStack &S)
{S.base=new int[MAXSIZE];if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=MAXSIZE;return OK;
}int main()
{int ID[MAXSIZE],k=0,n;cout<<"请输入所有的ID号:(以-1结束)"<<endl;for(int j=0;;j++){    cin>>n;if(n==-1)break;ID[j]=n;k++;}int e,m;SqStack S;InitStack(S);
for(int i=0;i<k;i++){if(S.top==S.base){*S.top++=ID[i];}int num=*(S.top-1);if(num!=ID[i+1]&&i<k-1){e=*--S.top;i++;}else{*S.top++=ID[i+1];}if(i==k-2){num=*(S.top-1);cout<<"水王的Id号为:"<<endl;cout<<num<<endl;}}return 0;
}

4.截图。

 

5.心得体会。

对于一些问题，可以剑走偏锋，不一定走老路，可以开发创新，从别的方面出发从而实现问题。