1 題目描述

給一個數組，存在一個數字超過半數，找出這個數。
這題有個特殊要求，就是要線性的時間複雜度，空間複雜度是O(1)。
因此難度會在空間複雜度如何滿足1的情況下，找出最佳解法。

2 解法

2.2 我的解法

一開始我沒看到有空間複雜度的限制，所以就很直接的使用了HashTable，把每個數字出現的次數記錄下來，最後找出最大的那個。

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        num_dic = {}
        threshold = len(nums) / 2
        # 計算每個數字出現的次數
        for i in range(len(nums)):
            if num_dic.get(nums[i]):
                num_dic[nums[i]] += 1
            else:
                num_dic[nums[i]] = 1
            # 一但發現有超過半數的數字，就直接返回
            if num_dic[nums[i]] > threshold:
                return nums[i]
        return None

時間複雜度O(n)

計算每個數字出現的次數，部分通過一次 for 循環遍歷整個 nums 列表，時間複雜度為 O(n)。

空間複雜度O(n)

空間複雜度由字典 num_dic 最壞的狀況下需要存儲 n 個不同的數字，因此空間複雜度為 O(n)。
和固定空間變量 threshold、i、k 和 v 使用固定的額外空間
因此總的空間複雜度是 O(n)。

可惜沒滿足題目要求的空間複雜度，所以這個解法是不合格的。

2.2 摩爾投票法

這是1980 由 Boyer 和 Moore 兩人所提出的算法：英文是 Boyer-Moore Majority Vote Algorithm。這個函數實現了 Boyer-Moore 多數投票算法，這是一種在線性時間和常數空間內找到多數元素的方法。

他的思想很簡單，假設存在一個數字超過半數，而每個數字代表一個生物組群好了。(e.g. 1 = 恐龍, 2 = 獅子, 3 = 老虎, …) 現在有一組串列，[1, 1, 2, 3, 1] 透過指標的方式，循序比較，遇到自己人就+1，遇到其他物種就開打，因為戰鬥力一樣所以雙方人馬都一起滅絕，經過物競天擇後，數量仍然 > 1的就是倖存者也就是數量最多的族群。

大概是這種感覺：

class Solution(object):
    def majorityElement3(self, nums):
        count = 1
        boss = nums[0]
        for i in range(len(nums)-1):
            next = nums[i+1]
            if count == 0:
                boss = next
                count = 1
                continue
            else:
                if boss == next:
                    count += 1
                else:
                    count -= 1
        return boss