(Leet Code c++)Majority Element

169. Majority Element

 

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

 

Example 1:

Input: nums = [3,2,3] Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2] Output: 2

 

Constraints:

• n == nums.length
• 1 <= n <= 5 * 104
• -231 <= nums[i] <= 231 - 1

주어진 벡터 배열 안에서 빈도수가 많은 숫자를 찾으면 된다.

map을 이용.

 

for문으로 nums를 순회하면서 원소의 빈도를 map에서 늘려주도록 한다.

그리고 map을 순회하면서 가장 많이 나온 수를 찾아 갱신하면 된다.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int answer = 0;
        int cnt = 0;
        map<int, int> m;
        
        for(int i = 0; i < nums.size(); i++){
            m[nums[i]]++;
        }
        
        for(auto itr = m.begin(); itr != m.end(); itr++){
            if(cnt < itr->second){
                answer = itr->first;
                cnt = itr->second;
            }
        }
        
        return answer;
    }
};