LeetCode/169.Majority Element

Boyer-Moore Majority Vote Algorithm. Search majority on streaming data. 즉, 스트리밍 데이터처럼 선형적인 데이터 상에서 과반수를 찾는 알고리즘이다.

이 알고리즘의 조건은 선형 데이터 상에서 반드시 과반수인(절반 !초과!) 값이 있어야 한다.

1. Count가 0일때, 아닐때로 구분할 수 있다. Count가 0이라면 초기화 상태나 마찬가지인 것이고, 새롭게 등장한 녀석이 major가 된다. -> 반드시 과반수인 값이 있으므로 과반수인 녀석이라면 count가 0이 될 일이 없으므로 여기에 들어왔다는 것은 이전의 major 값은 과반수가 아니라는 뜻이므로 밀어버리고 이번에 들어온 num이 과반수가 아닌지를 체크해야 한다.

2. Count가 0이 아니라면 같은지 확인해서 ++ 해주고 아니라면 -- 해준다.

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