題目:

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.

給定一個長度為n的陣列,返回它的majority element(出現>n/2次的值)

最初想法就是建立一個dictionary紀錄各數出現的次數
最後看哪個數出現了n/2次以上即為majority element

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        d={}
        for i in nums:
            if i in d:
                d[i]=d[i]+1
            else:
                d[i]=1
        for i in d:
            if d[i]>len(nums)/2:
                return i

最後執行時間185ms(faster than 81.70%)

不過一個一個計數實在有點慢
後來我想到既然確定majority element會出現n/2次以上
那在陣列為排序陣列的狀況下,中間必然為majority element
於是有了以下簡短的程式碼

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2]

最後執行時間159ms(faster than 99.16%)

看了討論區才發現題目其實是要用博耶-摩爾多數投票算法（Boyer–Moore majority vote algorithm）
該演算法概念是紀錄陣列第一位並從其開始遍歷,且設立計數器
若遇到和紀錄值一樣的值計數器+1,不一樣的值計數器-1
當計數器為0時,紀錄值轉為此時遇到的新值
若有個元素佔了陣列一半以上,最後的紀錄值便是該元素
總之就是讓各不同元素相互抵消最後只留下majority element
在這題實作如下

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        ans=0
        cnt=0
        for i in nums:
            if cnt==0:
                ans=i
            if ans==i:
                cnt=cnt+1
            else:
                cnt=cnt-1
        return ans

最後執行時間165ms(faster than 97.56%)

本題學習到的重點:博耶-摩爾多數投票算法（Boyer–Moore majority vote algorithm）
那我們下題見