169. 求众数

目录

题目描述

给定一个大小为n的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的,并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2

思路

其实可以使用反证法来论证这样得到的结果一定是众数,如果不是,则真正的众数一定被抵消掉了,如果把数组中的数分为两类:众数,其他数
最极端的情况,所有的其他数和众数发生抵消行为(因为也会发生其他数之间的抵消行为),因为众数过半,所以到最后是抵消不完的,一定最后剩下的是众数,这与我们假设最终得到的是非众数发生矛盾。

摩尔投票法
说白了就是不同元素之间的抵消(可以直观的认为不同元素之间的抵消,符合交换律和结合律),最后剩下的就是要求的目标,这里需要区分的是,摩尔算法不能确保得到的一定是众数(mode)(只有众数一定存在时摩尔算法得到的才是众数),
例如数组:[1,1,1,2,2,3,3,4,4],摩尔算法得出最后的结果应该是4,但4并不是众数,那是因为,大多数是指出现次数过半的数,而这个数组中没有这样的数,所以摩尔算法是是失效的,对于这种情况采取需要重新投票。

代码实现

class Solution {
public:
    int majorityElement(vector<int>& nums) {

    	int n = nums.size();
    	int ret = -1;
    	int cnt = 0;
    	for(int i = 0;i < n;i++)//流式处理
    	{
    		if(cnt == 0)//流式处理,进来时先进行判断再决定要进行的操作
    		{
    			ret = nums[i];
    			cnt = 1;
    		}
    		else 
    		{
    			if(nums[i] == ret)
    				cnt++;
    			else
    				cnt--;
    	    }
    	}
    	return ret;       
    }
};
上一篇:win10查看连过的WIFI密码


下一篇:【leetcode第 169 场周赛】5295. 和为零的N个唯一整数