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

Thanks for the solutions!

ReplyDeleteDid the same (y)

ReplyDelete