HDU 1029 Ignatius and the Princess IV

正文索引 [隐藏]

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1029

题目翻译

给一个长度为奇数的序列,求一个在序列中出现(n + 1) / 2次的数字。

题解

智力题
如果一个数字出现的(n + 1) / 2次,那么他出现的次数可以抵消其他所有数
所以,我们记录一个Num , Cnt .
如果下一个数是Num则Cnt ++否则Cnt–(如果Cnt==0,那么Num更新成这个数,Cnt=1)

代码