題目連結: Majority Element

題目描述為: 給定一個陣列大小為 N，要我們找出裡面出現超過 N/2 次的元素。

思路 1: Hash 法

設陣列大小為 N ，我們可以建立一組 map 來記錄該陣列裡面的元素出現次數，當出現超過 N/2 時，該元素即為所求。

• 複雜度評估
  當陣列大小為 N 時，至多需要遍歷整個陣列，時間複雜度為 O(N)，此方法另外建立了一組map來記錄元素是否出現過，空間複雜度為 O(N)。

參考程式碼

func majorityElement(nums []int) int {
    
    m := make(map[int]int)
    half:=len(nums)/2
   
    for _,v:=range nums{
        m[v]++
        if m[v]> half{
            return v
        }
        
    }
    
    return -1    
}

思路 2: Boyer–Moore 投票法

我們可以先假定一個元素為候選者，並統計它的出現次數，當遇到相同值時次數加 1，遇到不同值時次數 -1，若次數歸零則讓下一個元素為新的候選者。因為過半數元素存在，故最後候選者一定會是該元素。

• 複雜度評估
  當陣列大小為 N 時，至多需要遍歷整個陣列，時間複雜度為 O(N)，此方法只使用了常數個變數，與 N 大小無關，空間複雜度為 O(1)。

參考程式碼

func majorityElement(nums []int) int {
    candidate:=nums[0]
    count:=0
    
    for _,v:=range nums{
        
        if count==0{
            candidate=v
            count++
            continue
        }
        
        if candidate==v{
            count++
        }else{
            count--
        }
        
    }
    
    return candidate
}

小結:

方法 1 的應用情境極為廣泛，缺點是需要 O(N) 的空間複雜度。
方法 2 只需要 O(1) 的 空間複雜度，為此題的理想解法。而方法 2 經常被用來尋找一組元素中是否存在過半數的元素。
我將各解法加上簡單的測試，上傳程式碼到此。

補充:

在計算機科學領域中，除了 Boyer-Moore 投票法，他們還提出了 Boyer-Moore字串搜尋演算法，用來尋找目標字串。