求众数[leetcode] --修改：添加摩尔投票方式实现

深藏阁楼爱情的钟 2022-03-10 04:26 163阅读 0赞

### 问题描述： ###

给定一个大小为 *n *的数组，找到其中的众数。众数是指在数组中出现次数**大于** `⌊ n/2 ⌋` 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

**        示例 1:**

输入: [3,2,3]
          输出: 3

**        示例 2:**

输入: [2,2,1,1,1,2,2]
           输出: 2

### 分析： ###

根据众数的定义，在一个长度为n的数组中出现次数大于n/2，如实例1 所示 当元素排序后数组变成 【2，3，3】3的数量大于数组长度的一半也就是说在数组长度为奇数时，中间元素即为众数，当数组元素为偶数时，如【1，1，1，2，2，2，2，2】可以通过判断第一个数是否和n/2的数相等，如果相等第一个数即众数，否则最后一个数为众数。

### 代码： ###

###        ###

class Solution {
        public int majorityElement(int[] nums) {
            Arrays.sort(nums);
            if(nums.length % 2 == 0){
                if(nums[0] == nums[nums.length/2])
                    return nums[0];
                else
                    return nums[nums.length/2];
            }
            else
                return nums[nums.length/2];
        }
    }

### 摩尔投票法（Moore Voting）： ###

摩尔投票法的实现前提是数组中一定要有众数存在，思路是让数组中不相等的数两两抵消，这样到最后剩下的不能抵消的数字即为众数。

思路是先假定第一个数字为众数，使ans=nums\[0\]，然后计数器count++。接下来用ans和数组中下一个数字比较 如果相等则count++，不相等则count--，当count=0的时候，将下一个数值存入ans当作候选众数。

用\[1,2,1,,3,1,1,4\]举例：

先将1存入ans，count++后为1，1现在为第一个数所以不能抵消

遍历到2 ，ans 不等于2 所以1和2抵消，count --后为0

遍历到1，此时count为0，所以ans被更新为1，count为1

遍历到3，ans不等于3所以1和3抵消，count--后为0

遍历到1，count为0，ans更新为1，count++后为1

遍历到1，ans和1相等，count++后为2

遍历到4，ans和4不等，拿出一个1和4抵消，此时ans为1，count=1

### 代码： ###

int majorityElement(int[] nums){
            int ans = 0;
            int count = 0;
            for(int i = 0;i < nums.length;i++){
                if(count == 0){
                    ans = nums[i];
                    count ++;
                }
                else{
                    if(nums[i] == ans){
                        count++;
                    }else{
                        count--;
                    }
                }
            }
            return ans;
        }