Majority Element

#. Problem

Link

1. My approach

Just an easy for loop with a Map.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int size = nums.size();
        map<int, int> m;
        
        for(auto &num : nums){
            m[num]++;
            if(m[num] > size/2) return num;
        }
        // it won't reach here
        return 0;
    }
};

| Time(O(N)) | Space(O(1)) | | ———- | ———– | | 18 ms | 19.6 MB |

2. Boyer–Moore majority vote algorithm

Boyer–Moore majority vote algorithm is to get the candidate with the majority votes.

The Boyer–Moore majority vote algorithm is an algorithm for finding the majority of a sequence of elements using linear time and constant space.

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

Idea is to cancel out the same number, and when the count = 0, get new candidate and do the same thing till the end. It’s easier to understand to look at the picture.

3. Epilogue

What I’ve learned from this exercise:

• Boyer–Moore majority vote algorithm