leetcode-169 - Majority Element

動機

複習Counter與認識一個神奇的算法

Problem

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
• -231 <= nums[i] <= 231 - 1

Sol

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return Counter(nums).most_common(1)[0][0]

因為majority element會超過一半，所以會有連續的值 所以可以用一個counter紀錄連續相同的值，只要count等於0就換成現在的人

counter只會大於等於0的正數

class Solution:
    def majorityElement(self, nums):
        count = 0
        candidate = None

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

        return candidate