시간 복잡도를 고려하지 않는다면 배열을 정렬한 다음 가운데 원소를 구해 최소 O(nlogn) 시간에 답을 구할 수 있다.
그런데 O(n)의 시간과 O(1)의 공간 안에 답을 얻기 위해 어떻게 해야 할까?
Boyer-Moore Majority Vote 알고리즘을 사용하면 된다. 이 알고리즘은 선형 시간과 상수 공간을 사용해 배열의 majority 원소(배열 중 절반 이상인 원소)를 찾는 알고리즘이다.
찾아보니 KMP처럼 문자열 검색에서 많이 활용되는 듯 하다. 자세한 설명은 위키피디아랑 여기 읽어보기.
class Solution {
public:
int majorityElement(vector<int>& nums) {
int el = nums[0], cnt = 1, size = nums.size(), i;
for (i = 1; i < size; i++) {
(nums[i] == el) ? cnt++ : cnt--;
if (!cnt) {
el = nums[i];
cnt = 1;
}
}
return el;
}
};