169. Majority Element (top interview 150)

되게 쉬워보이긴 하는데, "  solve the problem in linear time and in O(1) space?" 이걸 고려해서 조금 더 생각해보자. 

 

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

 
Example 1:
Input: nums = [3,2,3]
Output: 3

Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
 
Constraints:
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

 

 

의식의 흐름:

dict써서 count하면 되지 않을까, 

 

아래와 같이 대충 짯다. 

class Solution:

    def majorityElement(self, nums: List[int]) -> int:

        arr = {}

        best = -1

        best_cnt = -1

        if len(nums)<=1:

            return nums[0]

        for i in nums:

            if i not in arr:

                arr[i] =1

            else:

                arr[i]=arr[i]+1

                if best_cnt < arr[i] and  arr[i] > len(nums)/2:

                    best = i

        return best

 

 

gpt한테 좀 더 좋은 코드를 짜달라고 해보자. 두근두근

def majorityElement(nums):
    count = 0
    candidate = None

    for num in nums:
        if count == 0:
            candidate = num
            count = 1
        elif candidate == num:
            count += 1
        else:
            count -= 1

    return candidate

 

오 " Boyer-Moore 다수결 투표 알고리즘" 이걸 사용한다고 한다.

이 알고리즘은 읽어보고 예시를 들면,

반장선거를 A,B,C가 한다고 하면,
A 가 나오면 후보자에 A를 올리고, 

그 다음 B가 나오면 A 투표된 값에서 하나 깍는다. 

각 후보자를 끌어내리려는 구조 느낌으로 이해하면 되겠다. 

 

추가적으로 생각해볼만한게, 

[4, 4, 4, 3, 3, 2, 2]

아래와 같은 경우에는 boyer-moore알고리즘이 성립 안할것 같았는데, 

⌊n / 2⌋ + 1, 즉 4번 이상 출현해야하니, 성립되지 않는게 맞다.