169 Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than $$\floor{\frac{n}{2}} \newcommand{\floor}[1]{\lfloor #1 \rfloor}$$ times.

• You may assume that the array is non-empty and the majority element always exist in the array.

Solution:
Brute-force solution with $$O(N)$$ space and linear time.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        map<int, int> record;
        int n = nums.size();
        for ( int i = 0; i <= n-1; i++ ) {
            if ( record.find(nums[i]) == record.end() ) record[nums[i]] = 1;
            else record[nums[i]] += 1;
            if ( record[nums[i]] >= n/2 + 1 ) return nums[i];
        }
        return nums[0];
    }
};

Smart solution with $$O(1)$$ space and linear time.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        int curr = nums[0];
        int i = 1, icount = 1;
        while ( i <= n-1 ) {
            if ( icount == 0 ) {
                curr = nums[i++];
                icount = 1;
                continue;
            }
            if ( nums[i] == curr ) icount += 1;
            else icount -= 1;
            i += 1;
        }
        return curr;
    }
};

Notes:
Follow-up question, what about $$\floor{\frac{n}{3}} \newcommand{\floor}[1]{\lfloor #1 \rfloor}$$?

• How many $$\floor{\frac{n}{3}} \newcommand{\floor}[1]{\lfloor #1 \rfloor}$$ majority elements could there be?