Skip to content

Latest commit

 

History

History
85 lines (55 loc) · 1.96 KB

majority-element.md

File metadata and controls

85 lines (55 loc) · 1.96 KB
title last_updated keywords sidebar comments permalink
Majority Element
Feb 22, 2022
algorithm
mydoc_sidebar
true
majority-element.html

#. 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

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.

Time(O(N)) Space(O(1))
25 ms 19.6 MB

3. Epilogue

What I've learned from this exercise:

  • Boyer–Moore majority vote algorithm