169. Majority Element

catepk·2021년 8월 28일
0

LeetCode

목록 보기
83/88
post-thumbnail

169. 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.

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 * 10^4
-2^31 <= nums[i] <= 2^31 - 1

풀이

-----dynamic programming-----

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        counts = collections.defaultdict(int)
        for num in nums:
            if counts[num] == 0:
                counts[num] = nums.count(num)
            if counts[num] > len(nums) // 2:
                return num

-----divide and conquer-----

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        if not nums:
            return 
        if len(nums) == 1:
            return nums[0]
        half = len(nums) // 2
        a = self.majorityElement(nums[:half])
        b = self.majorityElement(nums[half:])
        return[b, a][nums.count(a) > half]å

-----other way-----

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return sorted(nums)[len(nums) // 2]
profile
hello

0개의 댓글