[面试题] 17.10. 主要元素

[frdmu]

数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -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

解法一：
用Hash Table记录每个元素的出现次数。但是空间复杂度不是O(1)，代码如下：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> hash;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            hash[nums[i]]++;
        }
        for (auto it = hash.begin(); it != hash.end(); it++) {
            if (it->second > n / 2)
                return it->first;       
        }
        return -1;
    }
};

解法二：
官方题解提供了一种方法：摩尔投票法。
基本思路是：

• 维护一个candidate变量和cnt变量
• 遍历数组
  • 如果cnt == 0，将此时的元素e赋给candidate
  • 如果cnt != 0，如果candidate == e，cnt++，否则，cnt--
• 再次遍历数组
  若candidate的出现次数大于一半，则candidate就是主要元素，否则，主要元素不存在
  代码如下：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = -1, cnt = 0;
        
        for (auto e: nums) {
            if (cnt == 0) {
                candidate = e;
                cnt++; 
            } else {
                if (e == candidate) {
                    cnt++;
                } else {
                    cnt--; 
                } 
            } 
            
        }
        cnt = 0;
        for (auto e: nums) {
            if (e == candidate)
                cnt++;   
        }
        
        return  cnt > nums.size()/2 ? candidate : -1;
    }
};

类似题目：
229. Majority Element II