題目

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.

  • Follow-up: Could you solve the problem in linear time and in O(1) space?
  • 題目連結

Example 1

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

Example 2

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

解釋題目

給你一個 array，叫 nums，array 的長度是 n。找出「多數元素」，也就是 出現次數 > n/2 的元素。題目假設 nums 中必定存在多數元素。另外的延伸題是，是否能用 O(1) space 的方式解題。

思路 (1)

這題最直覺的想法就是開一個空的 dict 物件，記錄每個數字出現的數字在物件裡面。然後再遍歷物件，找出次數 > n/2 的多數元素。但是，這樣的空間複雜度是 O(n)，因為如果 n 越大，要開的空間越多。

程式碼 (1)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        majority = len(nums) / 2
        counter = dict()
        for i in range(0, len(nums)):
            if nums[i] in counter:
                counter[nums[i]] += 1
            else:
                counter[nums[i]] = 1

        for key, value in counter.items():
            if value > majority:
                return key

思路 (2)

然而，這樣寫法的「空間複雜度」是 O(n)。也就是在最壞情況下，nums 中的所有元素都是唯一的，那麼字典 counter 需要存儲 n 個不同的鍵值對。也就是說 nums 如果越長，需要的空間就會越多。O(1) 的概念是，不論 array 多長，我只需要固定數量的變數，就可以找出多數元素。

  1. 這題是有名的摩爾投票法（Moore Voting Algorithm）演算法。

  2. 主要是用「抵消」的概念，將可能的多數元素與其他元素進行「抵消」，因為 nums 一定存在「多數元素」，也就是出現次數超過陣列長度一半的那個值。

    不用去管當下誰是多數元素，而是去管：只要相鄰元素是不同元素，就兩兩做抵銷，最後留下的數字就會是多數元素。抵銷的元素，未必是要「多數元素」跟「非多數元素」，也有可能兩個都是「非多數元素」。

程式碼 (2)

  • 只利用 count 跟 candidate 兩個變數，去記錄抵銷的過程，所以不管 nums 有多長，我永遠只要這兩個變數的空間，所以空間複雜度是 O(1)。
  • 每個元素會去判斷兩個條件:
    1 candidate 的數量或庫存 ( count ) 是否為 0
    2 當下元素是否為 candidate
  • 當 count = 0，代表 candidate 被抵銷完了，庫存沒了，當前的 candidate 可能不是多數元素，所以 candidate 要換成當下遍歷到的元素。
  • 當下元素 ( num ) 等於 candidate，count = count + 1，代表庫存不用被抵銷。
  • 當下元素 ( num ) 不等於 candidate，count = count - 1，代表庫存被抵銷。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = None
        count = 0

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