Majority Element

+10

길이가 n인 정수 배열 nums가 주어집니다. 배열에서 한 값이 n / 2번보다 많이 나타나며, 그 값을 과반수 원소라고 합니다. 그 값을 반환하세요. 배열의 절반보다 많이 차지하는 값은 항상 유일하므로 답은 정확히 하나입니다.

함수

majorityElement(nums: integer-array) → integer

numsinteger-array: 정수 배열에서 하나의 값이 배열의 절반을 초과하여 차지하는 경우
반환값integer: n / 2회보다 더 많이 나타나는 값

제약 조건

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
하나의 값이 nums.length / 2번보다 많이 나타납니다.

예제

입력: nums = [3, 9, 3, 3, 4]
출력: 3
설명: 5개의 요소에서 3은 세 번 나타납니다. 3은 5 / 2 = 2.5보다 크며, 9와 4는 각각 한 번씩 나타납니다.

제출 시 숨은 테스트 +15개

후속 질문

배열을 정렬하지 않고 O(n) 시간과 O(1) 추가 메모리로 과반수 원소를 찾을 수 있나요?

풀이

각 값이 몇 번 나타나는지 세면 질문에 답할 수 있지만, 횟수를 세려면 해시 맵이 필요합니다. 해시 맵 없이 해결하는 방법은 다수 원소가 특별한 이유를 살펴보는 것입니다. 다수 원소는 다른 모든 값을 합친 것보다 더 많이 나타납니다. 다수 원소의 각 복사본을 다른 값 하나와 짝지어 둘 다 지우면, 다수 원소의 복사본이 항상 일부 남습니다. Boyer-Moore 투표 알고리즘은 후보 하나와 카운터 하나를 사용해 한 번 순회하면서 이 짝짓기를 수행합니다.

해시 맵으로 세기

핵심 아이디어

배열을 순회하면서 각 값이 나온 횟수를 기록하는 해시 맵을 유지합니다. 값의 횟수에 1을 더한 다음, 그 횟수가 배열 길이의 절반보다 커졌는지 확인합니다. 이 기준을 처음 넘는 값이 과반수 값이므로 즉시 반환할 수 있습니다.

[3, 9, 3, 3, 4]에서 3의 횟수는 인덱스 0에서 1, 인덱스 2에서 2, 인덱스 3에서 3이 됩니다. 5개 중 3개는 2.5보다 많으므로 마지막 원소를 읽지 않고 3을 반환합니다.

해시 맵 조회와 갱신은 평균적으로 O(1)이므로 시간 복잡도는 O(n)입니다. 맵에는 서로 다른 값이 최대 약 n / 2개 저장될 수 있으므로 추가 메모리 복잡도는 O(n)입니다. 다음 방법에서는 맵을 없앱니다.

알고리즘

값에서 개수로 매핑하는 빈 맵을 만듭니다.
각 요소 x에 대해 x의 개수에 1을 더합니다.
그 개수에 2를 곱한 값이 배열의 길이보다 크면 x를 반환합니다.

def majorityElement(nums):
    counts = {}
    for x in nums:
        counts[x] = counts.get(x, 0) + 1
        if counts[x] * 2 > len(nums):
            return x

보이어-무어 투표

핵심 아이디어

배열을 선거라고 생각해 보세요. 아직 상쇄되지 않은 표의 candidate 하나와 그 표의 count를 유지합니다. 후보와 같은 요소는 표를 하나 더합니다. 다른 요소는 표를 하나 취소하고, 두 요소는 함께 경쟁에서 탈락합니다. 카운트가 0이면 다음 요소가 새로운 후보가 됩니다.

마지막에 남은 값이 과반수인 이유는 무엇일까요? 취소할 때마다 서로 다른 두 값이 제거되므로 과반수 값은 최대 하나만 제거됩니다. 과반수 값이 m번 나타난다고 해 보겠습니다. 다른 요소는 n - m개뿐이며, 이는 m보다 적으므로 과반수 값을 모두 취소할 수 없습니다. 마지막까지 남아 있는 모든 표는 최종 후보의 표이고, 그중에는 과반수 값의 표도 있으므로 후보가 과반수 값입니다.

[8, 8, 1, 1, 8, 1, 8]에서는 카운트가 1, 2, 1, 0으로 변합니다. 1 두 개가 8 두 개를 취소한 것입니다. 다음 8은 카운트 1로 다시 시작하고, 그다음 1이 이를 취소하며, 마지막 8이 다시 후보가 됩니다. 8을 반환합니다. 변수 두 개를 사용해 한 번 순회하면 시간 복잡도는 O(n), 메모리 사용량은 O(1)입니다.

알고리즘

candidate를 첫 번째 요소로 설정하고 count를 0으로 설정합니다.
각 요소 x에 대해 count가 0이면 x를 후보로 지정합니다.
x가 후보와 같으면 count에 1을 더합니다. 그렇지 않으면 1을 뺍니다.
마지막 요소를 처리한 후 candidate를 반환합니다.

def majorityElement(nums):
    candidate = nums[0]
    count = 0
    for x in nums:
        if count == 0:
            candidate = x  # the old candidate's votes are used up
        if x == candidate:
            count += 1
        else:
            count -= 1  # x and one copy of the candidate cancel out
    return candidate

함정과 경계 사례

잘못된 답변은 대부분 정확히 절반인 경우를 처리하는 부분이나 카운터를 지나치게 해석하는 데서 나옵니다.

"절반 초과"는 엄격한 조건입니다. count >= n / 2는 4개 중 2개인 경우도 허용하므로, 이는 과반수가 아닙니다. count * 2 > n으로 비교하면 반올림이 문제를 일으킬 일이 없습니다.
Boyer-Moore에서 마지막 count는 과반수 원소가 몇 번 나타나는지를 나타내지 않습니다. [8, 8, 1, 1, 8, 1, 8]에서는 8이 네 번 나타나지만 count는 1로 끝납니다.
candidate = nums[0]과 count = 1로 시작하는 방식은 반복문이 인덱스 1부터 시작할 때만 작동합니다. 반복문을 인덱스 0부터 시작하면 첫 번째 원소가 두 번 투표합니다. [1, 2, 2]에서는 count가 0으로 끝나고 1을 반환합니다.
Boyer-Moore는 과반수가 있다는 보장에 의존합니다. 과반수가 없는 [1, 2, 3]에서도 3을 반환합니다. 입력에 과반수가 없을 수도 있다면, 후보를 신뢰하기 전에 두 번째 순회에서 후보의 개수를 세세요.

자주 묻는 질문4

보이어-무어 투표 알고리즘이란 무엇인가요?

O(1) 메모리로 한 번만 순회하여 목록의 절반을 초과하는 값을 찾습니다. 후보와 카운터를 유지합니다. 일치하는 요소가 나오면 카운터를 1 증가시키고, 다른 요소가 나오면 1 감소시키며, 카운터가 0이 되면 다음 요소가 후보가 됩니다. 다수 원소는 다른 모든 값을 합친 것보다 많으므로 끝에 남는 후보가 다수 원소입니다.

다수 원소의 시간 복잡도와 공간 복잡도는 얼마인가요?

Boyer-Moore 투표 알고리즘은 O(n) 시간과 O(1) 추가 공간을 사용합니다. 해시 맵을 사용한 카운팅도 O(n) 시간이 걸리지만, 카운트를 저장하는 데 O(n) 공간이 필요합니다. 먼저 정렬하면 O(n log n) 시간이 걸립니다.

정렬로 다수 원소 문제를 풀 수 있을까요?

네. 정렬한 후에는 과반수 원소의 모든 복사본이 배열의 절반보다 긴 하나의 블록에 모이고, 그런 블록은 모두 가운데 위치를 포함합니다. 따라서 아래로 내림한 n / 2 인덱스의 원소가 정답입니다. 작성하기는 간단하지만 O(n log n) 시간이 듭니다.

배열에 과반수 원소가 없을 수도 있다면 어떻게 해야 할까요?

Boyer-Moore는 배열의 절반을 초과하는 횟수로 나타나는 값이 없더라도 항상 후보를 반환합니다. 두 번째 순회를 추가해 후보의 개수를 세고, 그 개수가 n / 2보다 클 때만 후보를 받아들입니다. 전체 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 유지됩니다.

Python

def majorityElement(nums):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

입력

nums = [3, 9, 3, 3, 4]

기대값