[Easy] 배열에서 과반이 넘는 요소 찾기 - 169. Majority Element

다음은 배열 nums가 주어졌을 때, 과반수를 차지하는 요소를 반환하는 문제입니다.

과반수 요소는 배열의 크기 n의 절반 이상 나타나는 요소입니다. 배열에 항상 과반수 요소가 존재한다고 가정할 수 있습니다.

예제 1:

입력: nums = [3,2,3]
출력: 3

예제 2:

입력: nums = [2,2,1,1,1,2,2]
출력: 2

제약 조건:

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

추가 과제: 문제를 선형 시간 복잡도와 O(1) 공간 복잡도로 해결할 수 있습니까?

 

해결 방법:

이 문제를 해결하는 가장 직관적인 방법은 배열의 요소를 세고, 가장 많이 나타나는 요소를 반환하는 것입니다. 그러나 이 방법은 추가적인 공간 복잡도를 필요로 합니다.

 

추가 과제에서는 선형 시간 복잡도와 O(1) 공간 복잡도를 요구합니다. 이를 해결하기 위해 Boyer-Moore Voting Algorithm을 사용할 수 있습니다. 이 알고리즘은 현재 후보와 카운트를 사용하여 과반수 요소를 찾습니다.

Boyer-Moore Voting Algorithm 설명:

1. 두 개의 변수를 사용합니다: candidate와 count.
2. 배열을 순회하면서 count가 0인 경우 현재 요소를 새로운 candidate로 설정하고 count를 1로 설정합니다.
3. 현재 요소가 candidate와 같으면 count를 증가시키고, 그렇지 않으면 count를 감소시킵니다.
4. 마지막으로 candidate가 과반수 요소가 됩니다.

Python 코드 예제:

def majorityElement(nums):
    candidate = None
    count = 0
    
    for num in nums:
        if count == 0:
            candidate = num
        if num == candidate:
            count += 1
        else:
            count -= 1
    
    return candidate