思路
使用一个数和计数器来扫一遍数组
如果cnt为0且temp保存的数为当前扫描的第i个数,则计数器,否则将temp赋值为第i个数;如果cnt不为0,则temp与当前数相同则cnt,否则cnt–。
最后temp中存储的数一定为众数。
为什么这个思路是对的呢?因为众数一定是超过数组长度的一半的,那么最坏的情况就是该数的出现次数是k,其他数的出现次数是k-1,这样最后cnt里存储0,但是temp里存储的还是该众数。很容易理解,如果扫到最后一个元素的时候,这个元素与众数不相等,那么cnt为1,cnt减为0但是temp中存储的数不变,如果扫到最后一个数与众数相等,那么此时cnt一定为0,于是将temp重置为众数。
扩展问题
若将问题转变为,一村人当中好人的数量严格大于n/2,好人会如实回答问题,坏人则回答的真实性不可保证,这些村民之间知道互相的身份,请想出一个时间O(n)空间O(1)的询问策略。
思路还是一样的,当cnt为0的时候询问当前第i个数他自身是否是好人,如果是好人,则将temp置为当前数,否则不管(因为会回答自己是坏人的人只有坏人),如果cnt不为0,则询问当前数temp是否是好人,如果是则cnt++,否则cnt–。最后temp中保存的一定是好人,我们向他问出所有的人谁是好人谁是坏人就ok了。
class Solution {
public:
int majorityElement(vector<int>& nums) {
int temp=-1;
int cnt=0;
for(int i=0;i<nums.size();i++)
{
if(!cnt)
{
if(temp==nums[i])cnt++;
else temp=nums[i];
}
else
{
if(temp==nums[i])cnt++;
else cnt--;
}
}
return (int)temp;
}
};