主要元素 | 徐年の博客

力扣面试题 17.10. 主要元素

题目说明

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

示例

示例 1：

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

示例 2：

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

示例 3：

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

笔者理解

此题是一道数组算法问题，在力扣题库中被定义为简单题。

解法

当笔者阅读完此题后，笔者采用了，正反向选举的方式，如果一个数的出现超过半数，那么肯定他出现的次数可以抵消掉其他所有出现的数的次数，依照此规律，我们仅需两次遍历就可以把主要元素找出来，让我们来看看具体如何实现的吧。

实现

class Solution {
    /*
     * 数组
     * 计数
     */
    public int majorityElement(int[] nums) {
        int n = nums.length;

        int result = 0;

        // 出现最多的数和出现次数
        int mostNum = 0;
        int mostCount = 0;
        
        // 如果一个数次数出现最多，那么他的出现次数减去其他数出现的次数肯定大于0
        for (int i = 0; i < n; i++) {
            if (mostCount == 0) {
                mostNum = nums[i];
                mostCount++;
            }
            else {
                if (mostNum == nums[i]) {
                    mostCount++;
                }
                else {
                    mostCount--;
                }
            }
        }

        // 所有数的可能次数相互抵消了，没有主要元素
        if (mostCount == 0) {
            return -1;
        }

        result = mostNum;
        mostNum = 0;
        mostCount = 0;

        // 一次正向遍历可能出现特殊情况导致，主要元素审查失败
        // 再反向遍历一次，保证主要元素选举正确
        for (int i = n - 1; i >= 0; i--) {
            if (mostCount == 0) {
                mostNum = nums[i];
                mostCount++;
            }
            else {
                if (mostNum == nums[i]) {
                    mostCount++;
                }
                else {
                    mostCount--;
                }
            }
        }

        // 反向遍历所有数抵消或者与正向选举出的数不一样，主要元素不存在
        if (mostCount == 0 || result != mostNum) {
            return -1;
        }

        return result;
    }
}