iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 23
2
Software Development

從LeetCode學演算法系列 第 23

[Day 23] 從LeetCode學演算法 - 0169. Majority Element (Easy)

目標:
這題主要目的在於介紹一個特別的演算法,
它叫做Boyer–Moore majority vote algorithm(摩爾投票算法)
同時,接下來也會多介紹幾題陣列操作相關的題目。

原題:

Question:
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 exists in the array.
Example 1:
Input: [3,2,3]
Output: 3
Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2

分析/解題:
嗨,大家今天過得好嗎?歡迎回到軟工宅宅(誤)。
接下來的幾題我們會著墨一下有關陣列(Array)或列表(List)相關的內容。

題目給定了一個長度為n的陣列,
已知當中有一個majority element(佔大多數的元素),
這個數的個數會多過於⌊ n/2 ⌋。
(此符號代表向下取整數,如⌊ 5/2 ⌋=2。
別忘了是more than,所以如果n是5的話,
代表majority element至少要有3個)

題目還貼心地告訴我們,可以假定陣列不是空的,
且一定存在majority element,所以這邊可以省掉一些常用的檢查。

怎麼解這題呢?
一般來說的直覺可能會想使用HashMap來解(Python則用dict),
將每個數塞入HashMap/字典中,最後找最大的那個數就是了。
這麼做的時間複雜度為O(n),空間複雜度亦為O(n),
因為插入耗費的時間為O(1),插入n個數即為O(n),
同時,我們只能保證最多有n - ⌊ n/2 ⌋的不同種類的數,
所以空間上還是保持在O(n)的複雜度。
在中途過程中在去檢驗是否有超過半數的element也可以,
但由於過程不保證會先碰到超過半數,所以額外檢驗的時間,
和省下來後面可能不用做完的時間相比,是不能肯定誰效率比較好的。

那麼,有沒有比較節省空間的做法呢?
有的!這裡介紹一個演算法,全名叫做:
Boyer–Moore majority vote algorithm(摩爾投票算法)
這個算法的核心在於,
刪去一個數列中的兩個不同的數字,不會影響該數列的majority element。

假想有一群人要投票,候選人有A、B、C,假設A已知會過半數的話,
任取其中2個人取消他們的投票資格,會有以下的狀況:

  1. 被取消資格的是B跟C -> 顯然A還是過半數(而且比例更高了XD)
  2. 被取消資格的是(A, B)或(A, C) -> 一個投A的和一個不投A的同步被排除,
    所以無法改變A會過半數的狀況。

同理,在不只3個候選人(數字)的時候,每次取2個人取消投票資格(移除),亦無法改變投票結果(A還是會是majority element)。

註:
所以我們可以知道,當你跟你的家人政治立場不同時,
只有兩個人的狀況下都不去投票是沒有用的,
有用的方式是在投票前夕帶著跟你立場相反的家人們出國去玩
多於1人時,每多一個人你就多賺一張選票差距,但你的荷包可能會哭。
(不要說是我教的!)

依此,我們可以使用下列的方式來進行陣列運算:

  1. 取出第一個數放到一個暫存的變數(res),
    將計數器(cnt)設定為1,代表這個數出現1次。
  2. 取出下一個數nums[i],如果和res相等,則將計數器+1
    如果和res不同,且計數器>0時,將計數器-1;(代表取這兩個數成對移除)
    如果和res不同但是計數器=0時,將res更改為nums[i]並將計數器+1
    (代表res已經用完了,現在還沒被移除的是nums[i])
  3. 反覆進行步驟2直到陣列結尾,剩下的res即為答案。
    (因為兩兩移除到最後一定是非majority element的先被移光)

Java:

class Solution {
    public int majorityElement(int[] nums) {
        int res = nums[0], cnt = 1;
        
        // Boyer-Moore Voting Algorithm
        for (int i = 1; i < nums.length; ++i) {
            if (res == nums[i])
                cnt++;
            else if (cnt > 0)
                cnt--;
            else
                res = nums[i];
                cnt++;
        }
        return res;
    }
}

還有另一種作法,是將陣列進行排序,
無論如何majority element一定會通過中間的位置。
這種方式的時間複雜度為O(nlogn),空間複雜度視你的呼叫方式而定,
可能是O(1)也可能是O(n)(將排序的結果放到別的地方的話)

Python:

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        res, cnt, l = nums[0], 1, len(nums)
        for i in range(1, l):
            if res == nums[i]:
                cnt += 1
            elif cnt > 0:
                cnt -= 1
            else:
                res = nums[i]                
                cnt += 1
        return res
        
'''
# sorting solution
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return sorted(nums)[len(nums)//2]
'''

面試實際可能會遇到的問題:
「時間/空間複雜度?」
(O(n), O(1),除了一些變數以外我們沒有使用到額外的空間)

「各方法的優劣為何?」
(可以參照Solution的頁面,這篇作者分析的內容很完整)

從LeetCode學演算法,我們下次見囉,掰~

下篇預告:
0229. Majority Element II (Medium)


上一篇
[Day 22] 從LeetCode學演算法 - 0062. Unique Paths (Medium)
下一篇
[Day 24] 從LeetCode學演算法 - 0229. Majority Element II (Medium)
系列文
從LeetCode學演算法30

尚未有邦友留言

立即登入留言