题目描述
简单易懂,时间复杂度O(n),空间复杂度O(1)
C++ 代码
int moreThanHalfNum_Solution(vector[HTML_REMOVED]& nums) {
//最终的数次数在一半以上,每出现两个不同的数就消去这两个数,最终剩下的一定是所求的数。
int count=1,val=nums[0];//先假定这个数是第一个数,count记录他出现的次数
for(int i=1;i<nums.size();i++)
{
if (count==0)//当前假定的数被消去了,选下一个数
{
val=nums[i];
count++;
}
else if(val==nums[i])//相等 次数加1
{
count++;
}
else//不相等次数减一
count--;
}
return val;
}