[LeetCode] 169 | Majority Element | Python

---

문제 링크: https://leetcode.com/problems/majority-element/

---

문제

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.

---

조건

• n == nums.length
• 1 <= n <= 5 * 104
• $-2^{31}$ <= nums[i] <= $2^{31}$ - 1

---

내 풀이

O(1) space를 사용해서 풀려고 해봤다.

먼저 주어진 리스트(nums)를 정렬한다.

past에는 현재와 같은 원소가 시작하는 위치를 저장해둔다. (ex. [1,1,2,2,2,2]일 때, 현재 가르키는 원소가 1이라면 past=0, 현재 가르키는 원소가 2라면 past=2이다.)

현재 가르키는 원소가 바뀔 때(ex. 1에서 2로 넘어갈 때) 바뀌기 전 원소(1)의 갯수(n-past+1)가 len(nums)/2보다 크다면 이것을 리턴한다.

왜냐하면 majority element는 하나만 있다고 가정하기 때문이다.

for문을 한바퀴 다 돌아도 리턴값이 없다면 제일 마지막에 위치한 수를 리턴한다.

---

코드

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums = sorted(nums)
        past = 0
        
        for n, num in enumerate(nums):
            if num != nums[past]:
                if n-past >= len(nums)/2:
                    return nums[past]
                past = n
        
        return nums[-1]