LeetCode 169. Majority Element 문제 풀이

문제

Majority Element - LeetCode

문제 해결 방법

-O(n),O(1)으로 풀어야합니다

-언제나 majority element가 존재합니다.

-majority element의 정의는 list length/2 < element입니다

-아래 방법은 공간복잡도가 O(n)이므로 HashMap은 사용할수 없습니다.

1. 해쉬맵으로 모든 숫자개수를 카운트하며 어레이를 iterate합니다.
2. 카운트된 숫자가 가장 높은수를 찾아서 리턴합니다.

-아래방법은 시간 복잡도가 O(n log n)이므로 사용할수 없습니다.

1. 어레이를 정렬합니다.(Arrays.sort(nums);)
2. 어레이에서 nums[nums.length/2]를 리턴합니다.
3. 과반수 이상인 숫자가 존재하므로, 중간값은 반드시 과반수에 해당하는 값입니다.

그러므로, 이 문제는 유저가 O(n) 시간 복잡도와 O(1) 공간 복잡도로 해결하는 "보이어-무어 투표 알고리즘"을 알고있는지 확인하는 문제입니다.

이 알고리즘은 과반수 요소가 항상 존재한다는 가정을 기반으로 하며, 다음과 같이 동작합니다:

1. count 변수를 0으로 초기화하고 candidate 변수를 null로 설정합니다.**candidate**는 현재까지 과반수 요소로 추정되는 값입니다.
2. **count**는 현재까지 과반수 요소 후보로 선정된 값의 개수를 나타냅니다.
3. 배열을 순회하면서 다음을 수행합니다:현재 요소가 **candidate**와 같은 경우 **count**를 증가시킵니다.이렇게 하면 **count**는 현재까지의 순회 중에서 **candidate**와 동일한 요소의 개수를 나타내게 됩니다.
4. 주요 포인트는 다른 요소들이 **candidate**와 상쇄되어 **count**를 감소시키는 것입니다. 과반수 요소가 배열에서 가장 많은 요소를 차지하므로, 상쇄 과정을 통해 다른 요소들의 개수는 과반수 요소의 개수를 초과할 수 없습니다.
5. 현재 요소가 **candidate**와 다른 경우 **count**를 감소시킵니다.
6. **count**가 0인 경우 현재 요소를 **candidate**로 설정합니다.
7. 순회가 끝나면 candidate 변수에 저장된 값을 반환합니다. 이 값은 과반수 요소가 됩니다.

이 알고리즘의 핵심 아이디어는 과반수 요소가 반드시 다른 요소의 개수를 초과하기 때문에, 과반수 요소를 만나면 다른 요소와 그 수가 상쇄되기 때문에 최종적으로 과반수 요소만이 남게 됩니다.

시간복잡도: O(n), 공간복잡도: O(1)

https://github.com/eunhanlee/LeetCodeSolutions_169.MajorityElement.git

import java.util.NoSuchElementException;

public class Solution {
    /**
     * 주어진 배열에서 과반수 요소를 찾습니다.
     * 과반수 요소란 배열에서 ⌊n/2⌋ 보다 많이 등장하는 요소를 의미합니다 (여기서 n은 배열의 길이입니다).
     *
     * @param nums 입력 배열
     * @return 과반수 요소
     * @throws NoSuchElementException 과반수 요소를 찾을 수 없는 경우 발생
     */
    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            // count가 0일 경우, 현재 숫자를 후보로 지정합니다.
            if (count == 0)
                candidate = num;

            // 현재 숫자가 후보와 같다면 count를 증가시키고, 다르다면 count를 감소시킵니다.
            count += (num == candidate) ? 1 : -1;
        }

        // 과반수 요소를 찾지 못한 경우 NoSuchElementException을 발생시킵니다.
        if (candidate == null)
            throw new NoSuchElementException("과반수 요소가 존재하지 않습니다.");

        return candidate;
    }
}