169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

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

Example 1:

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

Example 2:

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

// Hashtable 
int majorityElement(vector<int>& nums) { // time: O(n); space: O(n)
    int n = nums.size();
    unordered_map<int, int> mp;
    for (int num : nums) {
        if (++mp[num] > n / 2) return num;
    }
    return -1;
}

// Moore Voting Method
int majorityElement(vector<int>& nums) { // time: O(n); space: O(1)
    int res = 0, cnt = 0;
    for (int num : nums) {
        if (cnt == 0) {
            res = num;
            ++cnt;
        } else {
            (num == res) ? ++cnt : --cnt;
        }
    }
    return res;
}

// Bit Manipulation
int majorityElement(vector<int>& nums) { // time: O(n); space: O(1)
    int res = 0, n = nums.size();
    long mask = 1;
    for (int i = 0; i < 32; ++i, mask <<= 1) {
        int bitCount = 0;
        for (int num : nums) {
            if (num & mask) ++bitCount;
            if (bitCount > n / 2) {
                res |= mask;
                break;
            }
        }
    }
    return res;
}

229. Majority Element II