[LeetCode] Majority Element (C++)

leetcode.com/problems/majority-element/

Majority Element - LeetCode

 

주어진 배열에서 과반수 이상 존재하는 원소가 있을 때, 이를 구하는 문제입니다. 

 

map을 활용할 경우, 주어진 배열의 빈도수를 전부 map에 기록하고, 빈도 수가 가장 큰 것을 찾으면 됩니다.

 

/* map 
 * time complexity : O(N)
 * space complexity : O(N)
*/

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> um;
        for(int i = 0; i < nums.size(); i++) {
            um[nums[i]]++;
        }
        
        int majority, maxx = 0;
        for(auto it : um) {
            if(it.second > maxx) {
                maxx =it.second;
                majority = it.first;
            }
        }
        
        return majority;
    }
};

 

정렬을 사용하는 경우, 과반수 이상 존재하는 원소는 배열에서 n/2에 위치할 수 밖에 없습니다. 따라서 정렬을 한 후, n/2번째 원소를 리턴하면 됩니다.

 

/* sorting 
 * time complexity : O(NlogN)
 * space complexity : O(1)
*/


class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        
        return nums[nums.size() / 2];
    }
};