과반수 득표 알고리즘 [Java]

과반수 득표 알고리즘

시간 : O(n)
공간 : O(1)

• https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm

투표 종료 후 둘중 하나는 참

• 과반수 득표가 존재하지 않는다.
• 과반수 득표는 answer이다.

코드

public static int majorityElement(int[] nums) {
        int answer = 0;
        int cnt = 0;
        for (int num : nums) {
            if (cnt == 0) {
                answer = num;
                cnt++;
            } else if (answer == num) {
                cnt++;
            } else {
                cnt--;
            }
        }
        return answer;
    }

참고 URL

• https://coder-in-war.tistory.com/entry/LeetCode-JAVA169-Majority-Element-%EA%B3%BC%EB%B0%98%EC%88%98%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
• https://www.youtube.com/watch?v=ZaQsnkKPFOs