[C++] LeetCode : Majority Element

Question

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.

size가 n인 배열이 주어질 때, majority 한 원소를 return 하라. 
majority 한 원소란, 전체 배열에서 n/2 이상 등장한 원소를 뜻한다. 
배열 안에 majority 원소가 항상 있다고 생각해도 좋다. 

 

제약사항

• n == nums.length
• 1 <= n <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9
   

---

Solution

문제를 풀 때 고려한 사항

• 배열의 크기는 최대 50000이다.
• 배열의 최소 크기는 1 이상이다. 
• 정확히 절반의 원소가 나타날 때 알고리즘이 정상적으로 동작하는가?

---

Solution1 

STL map을 사용하면 쉽게 해결할 수 있을 것 같다. 
이 코드는 1/2 개수 이상뿐만 아니라 그냥 최빈값을 찾는 코드이기도 하다. 

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        map<int, int> my_map;
		int majority = 0;
		int max_num = -1; 
		
		for(auto num : nums){
			if(my_map.find(num) != my_map.end()){
				my_map[num]++;
			}else{
				my_map[num] = 1;
			}
			
			if(my_map[num] > majority){
				majority = my_map[num];
				max_num = num;
			}
		}
		
		return max_num;
    }
};

• Time complexity : O(n) 
• Space Complexity : O(n) 

Solution2

문제에서 공간 복잡도 O(1)에 해결해볼 것을 권하고 있다. 
즉, map 등의 별도의 공간 사용 없이 해결해보란 것인데, 변수 몇 개로 해결해봐야 할 것 같다. 
majority 원소를 x라 하였을 때, 배열의 n/2 이상이 x라는 것을 의미한다.
그렇기 때문에 배열을 순차적으로 탐색하며, 해당 원소를 최빈값이라고 가정하고, 
최빈값이면 count를 증가, 최빈값이 아니면 count를 감소하여 count가 0이 된다면 최빈값을 교체해준다. 

해당 알고리즘은 이미 Boyer-Moore Voting Algorithm으로 유명하다. 
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm

Boyer–Moore majority vote algorithm - Wikipedia

class Solution {
public:
    int majorityElement(vector<int>& nums) {
		int count = 0;
		int majority = 0;
		
		for(auto num : nums){
			if(count == 0){
				majority = num;
			}
			count += ((majority == num) ? 1 : -1);
		}
		
		return majority;
    }
};

• Time complexity : O(n) 
• Space Complexity : O(1) 

출처 : https://leetcode.com/explore/interview/card/top-interview-questions-medium/114/others/824/

Explore - LeetCode