leetcode Question: Majority Element

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.

Analysis:

This a simple question that hashmap (dict) is all we need.
Construct a hashmap that the key is each element in the num, the value is the occurrence of num.
Check the value while constructing the map can get the result.

Code(C++):

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

Code(Python):

class Solution:
    # @param num, a list of integers
    # @return an integer
    def majorityElement(self, num):
        dict = {}
        for n in num:
            dict[n] = dict.get(n,0) +1
            if dict[n] > len(num)/2:
                return n