0169. Majority Element - chasel2361/leetcode GitHub Wiki

***Given an array of size n, find the majority element.
The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:
Input: [3,2,3]
Output: 3

Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2

這題主要目的是要求出現次數大於數列二分之一的值，這個問題可以用 python 的 dict 來解

[1] 如果取出的數不存在於 map 裡，就令其 value 為 0
[2] 如果取出的數存在 map 裡，就令其 value 為原本值 + 1

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        numMap = {}
        for n in nums:
            try:
                numMap[n] = numMap[n] + 1
            except:
                numMap[n] = 1
        res = max(numMap, key = numMap.get)
        return res

理論上這個題目應該要檢查 res 這個值是否有大於 nums 長度的一半，但我試了一下，發現他的題目設定只要求出次數最多的數就好，如果次數最多的數沒有大於長度一半還是會輸出，所以就變成這樣了。

這樣寫的話時間複雜度是 O(N), 空間複雜度也是 O(N)

另外，同樣的功能可以使用 collections.Counter，這是一個特別設計來計數的 dict，只要呼叫的 key 值不存在就會回傳 0 ，且 constructor 輸入值為 iterable ，所以不論是 list 或是 string 都可以，使用上也更加方便快速

from collections import Counter
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = Counter(nums)
        return max(count, key = count.get)

---

另外可以換個概念，如果待求的值出現次數必定大於 nums 長度的一半，那只要把 list 排序，取 index 為長度一半的值就可以了

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

這樣寫的話時間複雜度是 O(NlogN), 空間複雜度是 O(1)

---

最後要來提摩爾投票演算法 (Boyer-Moore Voting)

他的概念在於，如果已知有某個值出現次數大於二分之一，那我們任選兩個不同的數刪除，最後剩下的那個數一定是出現最多次的值。

這裡利用計數器的概念來代表數，

[1] 當取得不同數字時，就將計數器減一 (代表刪除當前取出之數以及對照數)
[2] 計數器為零時就將對照數換成取出數

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        res = nums[0]
        count = 1
        for i in range(1, len(nums)):
            if nums[i] == res:
                count += 1
            elif count > 0:
                count -= 1
            else:
                res = nums[i]
                count += 1
        return res

這個算法的時間複雜度是 O(N)，空間複雜度是 O(1)