Leetcode: Majority Element

Difficulty: Easy

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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

Hide Tags

 Divide and Conquer Array Bit Manipulation

Show Similar Problems

--------------------------------------

Frequency map:

////////////////////////////////

//codes

class Solution {

public:

    int majorityElement(vector<int>& nums) {

        unordered_map<int,int> fre;

        int len=nums.size(), mid=len/2;

        //build a frequency map

        for(int i=0;i<len;i++){

            fre[nums[i]]++;

            if(fre[nums[i]]>mid) return nums[i];

        }

    }

};