Majority Element II

https://leetcode.com/problems/majority-element-ii/description/

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Thoughts

超过1/3的可能有两个数。 因此用Moore's voting同时找出两个候选，因为假设两个存在，那抛去掉一个剩下一个在剩下的里头一定会count>0，所以可以继续用Moore's voting。由于题目说了不一定存在，再验证下候选。

Code

/*
 * @lc app=leetcode id=229 lang=cpp
 *
 * [229] Majority Element II
 *
 * https://leetcode.com/problems/majority-element-ii/description/
 *
 * algorithms
 * Medium (32.90%)
 * Likes:    990
 * Dislikes: 117
 * Total Accepted:    110.4K
 * Total Submissions: 335.1K
 * Testcase Example:  '[3,2,3]'
 *
 * Given an integer array of size n, find all elements that appear more than ⌊
 * n/3 ⌋ times.
 * 
 * Note: The algorithm should run in linear time and in O(1) space.
 * 
 * Example 1:
 * 
 * 
 * Input: [3,2,3]
 * Output: [3]
 * 
 * Example 2:
 * 
 * 
 * Input: [1,1,1,3,3,2,2,2]
 * Output: [1,2]
 * 
 */
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        const int N = nums.size();
        int a = 0, b = 0, ca = 0, cb = 0;
        for (const auto num : nums) {
            if (num == a) ++ca;
            else if (num == b) ++cb;
            else if (ca == 0) {
                a = num;
                ca = 1;
            } else if (cb == 0) {
                b = num;
                cb = 1;
            } else {
                --ca;
                --cb;
            }
        }
        ca = 0; cb = 0;
        for (const auto num : nums) {
            if (num == a) ++ca;
            else if (num == b) ++cb;
        } 
        vector<int> res;
        if (ca > N / 3) res.push_back(a);
        if (cb > N / 3) res.push_back(b);
        return res;
    }
};

Analysis

时间O(N).