[数据结构与算法]leetcode.面试题 17.10. 主要元素---摩尔投票法

面试题 17.10. 主要元素

数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。

示例 1：

输入：[1,2,5,9,5,9,5,5,5]
输出：5
示例 2：

输入：[3,2]
输出：-1
示例 3：

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

题解：

由于题目限制了时间和空间的复杂度，因此我们这里只能使用摩尔投票法进行解决，具体摩尔投票法思路可见开学回归力扣：第十一题——169. 多数元素（摩尔投票法）.

代码：

• 但是在实现的过程中，由于题目没有限制说一定含有“主要元素”，所以可能不含有，因此不能只是使用摩尔投票法，因为使用摩尔投票法最终得到的不一定是我们想要的元素。
• 比如当不含有“主要元素”时，我们发现，如[1，2，3，2]的序列，最后会剩下的2只是含有的最多的元素，不是“主要元素”；再比如[1,2,3]的序列，我们发现最后剩下的只是3，也不是“主要元素”，因此我们除了使用摩尔投票法进行选择之外还要进行一次验证过程。
• 所以需要记住，摩尔投票法求得的元素他的个数一定是不小于数组内别的元素的个数的！（因为也会像[1,2,3]一样）

验证方法一：正反双投票验证

• 即形如[4,3,2]，通过正反两次得到结果是不同的，而如果是“主要元素”怎么遍历都会得到一样的；

class Solution {
    public int majorityElement(int[] nums) {
        int flag = nums[0];
        int sum = 1;
        for(int i=1;i+1<nums.length;i++){
            if(flag == nums[i]){
                sum++;
            }
            if(flag != nums[i]){
                sum--;
            }
            if(sum == 0){
                flag = nums[i+1];
                i++;
                sum = 1;
            }
        }
        int flag0 = nums[nums.length-1];
        int sum0 = 1;
        for(int i=nums.length-2;i-1>=0;i--){
            if(flag0 == nums[i]){
                sum0++;
            }
            if(flag0 != nums[i]){
                sum0--;
            }
            if(sum0 == 0){
                flag0 = nums[i-1];
                i--;
                sum0 = 1;
            }
        }

        if(sum>=1 && flag0==flag)
            return flag;
        
        return -1;
    }
}

验证方法二：二次遍历得到flag个数通过除法验证

• 即投票得到最终的flag后，求一下其个数是否满足一半以上，但是由于使用除法会出现精度损失问题，这里使用巧妙的+0.5
  来进行四舍五入解决；

class Solution {
    public int majorityElement(int[] nums) {
        int flag = nums[0];
        int sum = 1;
        for(int i=1;i+1<nums.length;i++){
            if(flag == nums[i]){
                sum++;
            }
            if(flag != nums[i]){
                sum--;
            }
            if(sum == 0){
                flag = nums[i+1];
                i++;
                sum = 1;
            }
        }
        int temp = 0;
        for(int num:nums){
            if(num==flag){
                temp++;
            }
        }

        if(sum>=1 && temp>=(int)(nums.length/2.0+0.5))
            return flag;
        
        return -1;
    }
}

验证方法三：二次遍历得到flag个数通过乘法验证

• 避免了除法的精度损失；

class Solution {
    public int majorityElement(int[] nums) {
        int flag = nums[0];
        int sum = 1;
        for(int i=1;i+1<nums.length;i++){
            if(flag == nums[i]){
                sum++;
            }
            if(flag != nums[i]){
                sum--;
            }
            if(sum == 0){
                flag = nums[i+1];
                i++;
                sum = 1;
            }
        }
        int temp = 0;
        for(int num:nums){
            if(num==flag){
                temp++;
            }
        }

        if(sum>=1 && temp*2 >= nums.length)
            return flag;
        
        return -1;
    }
}

再附上力扣上大神的理解~