169. Majority Element

문제

길이가 n인 배열 nums에서 n/2번 이상 등장하는 숫자를 반환한다. n/2번 이상 등장하는 숫자는 반드시 존재한다고 가정하며, 아래 조건일 때 시간복잡도 O(n), 공간복잡도O(1)으로 해결해야 한다.

• n == nums.length
• 1 <= n <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9

나의 접근법

Boyer-Moore 과반수 투표 알고리즘을 사용했다.

class Solution {

    public int majorityElement(int[] nums) {
        int count = 0;
        int candidate = 0;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        count = 0;
        for (int num : nums) {
            if (num == candidate) {
                count++;
            }
        }

        return (count > nums.length / 2) ? candidate : -1;
    }
}

코멘트

다만, 이 문제의 경우 반드시 n/2번 이상 등장하는 숫자가 존재한다고 가정했는데, 과반수만큼 등장하는 숫자가 없다면 전혀 엉터리의 값을 내게 된다.