LeetCode - The World's Leading Online Programming Learning Platform

Intuition

Use a counter to represent the count of the 'previous number.'

Traverse the array. If the current number matches the counter's number, increment the counter; otherwise, decrement the counter.

When the counter reaches 0, it indicates that the frequency of the 'current number' is greater than the count recorded by the counter. Update the counter with the new number."

用計數器表示「前一個的數字」出現的數量。

走訪 array ，如果當前出現的數字與計數器的數字一樣的話，計數器就往上加，反之，計數器就往下減。

當計數器減至 0 時，表示「當前的數字」的出現次數比「計數器紀錄的數字」還要大，計數器更新成新的數字。

Approach

• Initialize a counter to keep track of the occurrences of nums[0], with a default value of 1.
• Iterate through nums, and for each element:
  • Check if the current element is equal to the counter's recorded number. If true, increment the counter; otherwise, decrement the counter.
  • When the counter reaches 0, update the "counter's number" to the current element.

Complexity

• Time complexity: O(n)O(n)O(n)
• Space complexity: O(1)O(1)O(1)

Code

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cur = nums[0]
        count = 1

        for i in range(1, len(nums)):
            if nums[i] == cur:
                count += 1
            else:
                count -= 1
                if count == 0:
                    cur = nums[i]
                    count = 1
        
        return cur

space: O(n) solution

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = defaultdict(int)
        for n in nums:
            count[n] += 1
            if count[n] > len(nums)//2:
                return n