LeetCode 229 Majority Element II

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.

Hint:

How many majority elements could it possibly have?

Diffculty
Medium

Similar Problems
[LeetCode 169] Majority Element Medium

Analysis

与Majority Elements不同是这里需要维护两个变量n1和n2，如果下一个数与这两个数都不同的时候， count1和count2都减一，如果下一个数与n1或者n2相等的时候，对应的count++。最后的结果必定在n1或者n2中。

Solutions

class Solution {
public:
    int majorityNumber(vector<int> A){
        int n1 = A[0], count1 = 1;
        int i = 1;
        for (; i < A.size() && A[i] == n1; i++){
            count1++;
        }
        if (i == A.size()){
            return n1;
        }

        int n2 = A[i], count2 = 1;
        for (int i = i + 1; i < A.size(); i++) {
            if (A[i] == n1) {
                count1++;
            } else if (A[i] == n2) {
                count2++;
            } else {
                if (count1 == 0) {
                    n1 = A[i];
                    count1 = 1;
                } else if (count2 == 0 && A[i] != n1) {
                    n2 = A[i];
                    count2 = 1;
                } else {
                    count1--;
                    count2--;
                }
            }
        }
        if (count1 == 0) {
            return n2;
        } else if(count2 == 0) {
            return n1;
        } else {
            int count = 0;
            for (int n : A) {
                if (n == n1) {
                    count++;
                }
            }
            if (count > A.size()/3) {
                return n1;
            }
            return n2;
        }
    }
}

The problem is similar to Boyer–Moore majority vote algorithm. First we can find that there are up to 2 elements that appear more than ⌊ n/3 ⌋ times. We divide the array as 3 numbers a group(obviously there are ⌊ n/3 ⌋ groups), then we believe that A must be an answer if A appears more than once in one group. After that we can use the Boyer–Moore majority vote algorithm‘s variant to solve this problem.

Boyer–Moore majority vote algorithm The Boyer-Moore Vote Algorithm solves the majority vote problem in linear time [O(n)] and constant memory [O(1)]. The majority vote problem is to determine in any given sequence of choices whether there is a choice with more occurrences than all the others, and if so, to determine this choice. Mathematically, given a finite sequence (length n) of numbers, the object is to find the majority number defined as the number that appears more than n/2 times. The algorithm is carried out in two steps:

1. Eliminate all elements except one. Iterating through the array of numbers, maintain a current candidate and a counter initialized to 0. With the current element x in iteration, update the counter and (possibly) the candidate:

If the counter is 0, set the current candidate to x and the counter to 1. If the counter is not 0, increment or decrement the counter based on whether x is the current candidate.

1. Determine if the remaining element is a valid majority element. With the candidate acquired in step 1, iterate through the array of numbers and count its occurrences. Determine if the result is more than half of the sequence’s length. If so, the candidate is the majority. Otherwise, the sequence doesn’t contain a majority.

class Solution{
public:
    vector<int> majorityElement(vector<int>& A)    {
        int len = A.size();
        int f = len / 3;
        vector<int> ans;
        int n1, n2, c1, c2;
        n1 = n2 = c1 = c2 = 0;

        // step I
        for(int i = 0; i < len; ++i){
            if(c1 == 0){
                n1 = A[i];
                c1 = 1;
            }
            else if(c2 == 0 && A[i] != n1){
                n2 = A[i];
                c2 = 1;
            }
            else if(A[i] == n1) c1++;
            else if(A[i] == n2) c2++;
            else
            {
                c1--;
                c2--;
            }
        }

        // step II
        c1 = c2 = 0;
        for(int i = 0; i < len; ++i){
            if(A[i] == n1) c1++;
            else if(A[i] == n2) c2++;
        }
        if(c1 > f) ans.push_back(n1);
        if(c2 > f) ans.push_back(n2);
        return ans;
    }
};

Reference