題目

  • 題目連結
  • 目標函式 : reverseList(head)
    • Input : head: ListNode
    • Output : ListNode

解題概念

  • 題意 : 給定一長度 n 的陣列 nums，需要回傳 Majority element
  • Majority element 定義 : 該元素個數超過 $\lfloor n/2 \rfloor$

我的寫法

  • 想法 : 我使用 Hashmap 與 for 迴圈去處理，在每次迴圈中 :
    • 紀錄該元素的個數 : 若該元素存在 Hashmap，則對應 value + 1，否則設定為 0
    • 如果目前該元素的數目已超過 $\lfloor n/2 \rfloor$，則可直接回傳
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    def majorityElement(self, nums):
        
        hashmap = dict()

        for i in nums:
            if i in hashmap:
                hashmap[i] += 1
            else:
                hashmap[i] = 1

            if hashmap[i] > len(nums) // 2:
                return i
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 153 ms (faster than 17.18%)
    • Memory Usage: 14.9 MB (more than 80.58%)

解答 or 其他優秀寫法

  • 想法 : 採用 Boyer-Moore Algorithm (多數投票演算法)
    • 簡單來說，先設定 major = nums[0] 與 counter = 1
      • major : 代表目前的 Majority Element
      • counter : major 目前記錄的數量
    • 運用迴圈針對每個元素 :
      • 若 counter == 0 : 代表當前 major 並非 Majority Element，因此將 nums[i] 設為 major，並將 counter = 1
      • 若 counter != 0 且 nums[i] == major : 代表當前 major 仍是 Majority Element，並將 counter ++
      • 若 counter != 0 且 nums[i] != major : 代表當前 major 仍是 Majority Element，並將 counter --
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    def majorityElement(self, nums):
        
        major = nums[0]
        counter = 1

        for i in range(1, len(nums)):

            if counter == 0:
                major = nums[i]
                counter = 1 # 或寫成 counter+=1 也可以
            else: # counter != 0
                if nums[i] == major:
                    counter += 1
                else: # nums[i] != major
                    counter -= 1
        
        return major
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 121 ms (faster than 96.66%)
    • Memory Usage: 15.53 MB (more than 12.02%)