[LeetCode] 229. Majority Element II

[frdmu]

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Follow-up: Could you solve the problem in linear time and in O(1) space?

 

Example 1:

Input: nums = [3,2,3]
Output: [3]

Example 2:

Input: nums = [1]
Output: [1]

Example 3:

Input: nums = [1,2]
Output: [1,2]

Constraints:

• 1 <= nums.length <= 5 * 104
• -109 <= nums[i] <= 109

 
 
 
 
解法一：
hashTable，但是不满足空间复杂度O(1)的要求。代码如下：

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

解法二：
摩尔计数法：选取候选人，计数。
我先自己试了一下，很难写出来，因为没有搞清楚选取候选人的逻辑，看了题解也有点蒙，于是翻了翻评论，看到一个有意思的评论Leetcode:龅牙叔，写的很好，这里摘抄一下：

有一个对摩尔投票法非常形象的比喻：多方混战。

首先要知道，在任何数组中，出现次数大于该数组长度1/3的值最多只有两个。

我们把这道题比作一场多方混战，战斗结果一定只有最多两个阵营幸存，其他阵营被歼灭。数组中的数字即代表某士兵所在的阵营。

我们维护两个潜在幸存阵营A和B。我们遍历数组，如果遇到了属于A或者属于B的士兵，则把士兵加入A或B队伍中，该队伍人数加一。继续遍历。

如果遇到了一个士兵既不属于A阵营，也不属于B阵营，这时有两种情况：

 - A阵营和B阵营都还有活着的士兵，那么进行一次厮杀，参与厮杀的三个士兵全部阵亡：A阵营的一个士兵阵亡，B阵营的一个士兵阵亡，这个不知道从哪个阵营来的士兵也阵亡。继续遍历。

 - A阵营或B阵营已经没有士兵了。这个阵营暂时从地球上消失了。那么把当前遍历到的新士兵算作新的潜在幸存阵营，这个新阵营只有他一个人。继续遍历。

大战结束，最后A和B阵营就是初始人数最多的阵营。判断一下A，B的人数是否超过所有人数的三分之一就行了。

根据这个思路，代码很容易就写出来了：

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
            int candidate1 = nums[0], candidate2 = nums[0], cnt1 = 0, cnt2 = 0;
            int n = nums.size();
            vector<int> res;
        
            for (auto e: nums) {
                if (candidate1 == e) {
                    cnt1++;
                } else if (candidate2 == e) {
                    cnt2++;
                } else {
                    if (cnt1 != 0 && cnt2 != 0) {
                        cnt1--;
                        cnt2--;
                    } else {
                        if (cnt1 == 0) {
                            candidate1 = e;
                            cnt1++;
                        } else {
                            candidate2 = e;
                            cnt2++;
                        }  
                    }                   
                }    
            } 
            cnt1 = 0, cnt2 = 0;
            for (auto e: nums) {
                if (e == candidate1) {
                    cnt1++;
                } else if (e == candidate2) {
                    cnt2++;
                }
            }
            if (cnt1 > n/3) res.push_back(candidate1);
            if (cnt2 > n/3) res.push_back(candidate2);
        
            return res;
    }
};

类似题目：
17.10. 主要元素