169. Majority Element

• 첫번째 숫자를 기준으로 숫자의 개수(count)를 센다.

• 만일 다른 숫자가 나오면 count를 감소시키고 count가 0이 되면 새로 출현한 숫자를 기준으로 개수를 센다.

• 과반 숫자는 항상 존재한다고 가정한다면 전체 array에서 과반 숫자의 수가 절반 이상일 것이므로 끝까지 세었을 때 과반 숫자의 count 값은 1 이상이 된다.
• 만일 과반 숫자가 없는 경우라면 이 알고리즘은 성립하지 않는다 (예: 어떤 두 숫자가 동등한 개수만큼 있는 경우).

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int elem = nums[0];
        int count = 1;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] != elem) --count;
            else ++count;
            if (count == 0) {
                elem = nums[i];
                count = 1;
            }
        }
        return elem;
    }
};