Additional constraint: Solve in linear time with O(1) space.

Intuition 🤔

왜 more than n/2 times 일까? [3, 3, 1, 2, 4]에서 3은 majority가 아니다. 왜 이런 setup을 골랐을까?
왜 항상 존재해야할까?
linear로 풀기 위해서는 어떻게 해야할까?

답안

class Solution {
    public int majorityElement(int[] nums) {
        int majorityNum = nums[0]; 
        int count = 1; 

        for (int index = 1; index < nums.length; index++) {
            if (majorityNum != nums[index]) {
                count -= 1; 
            } else {
                count += 1; 
            }

            if (count == -1) {
                majorityNum = nums[index];
                count = 1; 
            }
        }

        return majorityNum; 
    }
}

꽤나 쉽다.