iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 24
2
Software Development

從LeetCode學演算法系列 第 24

[Day 24] 從LeetCode學演算法 - 0229. Majority Element II (Medium)

目標:
這題主要目的在於進一步討論摩爾投票算法的延伸。

原題:

Question:
Given an integer array of size n,
find all elements that appear more than ⌊ n/3 ⌋ times.
Note: The algorithm should run in linear time and in O(1) space.
Example 1:
Input: [3,2,3]
Output: [3]
Example 2:
Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

分析/解題:
跟上一篇相似,這篇將出現超過二分之一改變為三分之一,
要求求所有出現超過三分之一次數的數值,
這使得可能超過三分之一的種類會變成2種,但並不保證一定會有2種。
按照上一篇的摩爾投票算法的思路,
我們可以取2個數(n1, n2)暫存,
每次拿一個新的來檢驗並處理每三個相消的動作,
這樣我們即可以保證留下來的會有當中超過三分之一的元素。

要特別留意的是,兩個數有可能會是一致的,
且不一定每次都存在2種超過三分之一的元素,
所以最後我們要個別重新確認留在n1及n2上的元素其個數是否有超過三分之一。

Java:

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if (nums == null || nums.length == 0)
            return res;
        int n1 = 0, n2 = 1, cnt1 = 0, cnt2 = 0;
        for (int num : nums) {
            if (num == n1) {
                ++cnt1;
            } else if (num == n2) {
                ++cnt2;
            } else if (cnt1 == 0) {
                n1 = num;
                cnt1 = 1;
            } else if (cnt2 == 0) {
                n2 = num;
                cnt2 = 1;
            } else {
                --cnt1;
                --cnt2;
            }
        }
        cnt1 = 0;
        cnt2 = 0;
        
        for (int num : nums) {
            if (num == n1) 
                ++cnt1;
            else if (num == n2)
                ++cnt2;
        }
        
        int len = nums.length;
        if (cnt1 > len / 3)
            res.add(n1);
        if (cnt2 > len / 3)
            res.add(n2);
        return res;
    }
}

Python的部分,我們這邊除了同於Java的解法以外,
再提供一個簡單的作法:使用Counter。
利用Counter可以將一個列表轉換成Counter物件,
儲存的方式是(key:元素 及 value: 該元素出現的次數)
在迴圈中的取用基本上跟字典類似。
只要檢查每個元素出現次數是否大於三分之一的數量即可加至結果。
(請留意如果認真按照題目要求的話,這個解法因為會佔用額外O(n)空間
故不是一個在O(1)空間內可以完成的算法。)

Python:

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        if not nums:
            return []
        n1, n2, cnt1, cnt2 = 0, 1, 0, 0
        for num in nums:
            if num == n1:
                cnt1 += 1
            elif num == n2:
                cnt2 += 1
            elif cnt1 == 0:
                n1 = num
                cnt1 = 1
            elif cnt2 == 0:
                n2 = num
                cnt2 = 1
            else:
                cnt1 -= 1
                cnt2 -= 1
        
        cnt1, cnt2 = 0, 0
        
        for num in nums:
            if num == n1:
                cnt1 += 1
            elif num == n2:
                cnt2 += 1
        
        res, l = [], len(nums)
        if cnt1 > l // 3:
            res.append(n1)
        if cnt2 > l // 3:
            res.append(n2)
            
        return res
                
'''
# Using Counter but need extra space
from collections import Counter
class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        constraint = len(nums) // 3
        count = Counter(nums)
        res = []
        for k, v in count.items():
            if v > constraint:
                res.append(k)
            
        return res
'''

面試實際可能會遇到的問題:
「時間/空間複雜度?」
(O(n), O(1)。
要經過整個陣列兩次,且額外並沒有需求常數次數以外的空間)

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

下篇預告:
0063. Unique Paths II (Medium)


上一篇
[Day 23] 從LeetCode學演算法 - 0169. Majority Element (Easy)
下一篇
[Day 25] 從LeetCode學演算法 - 0063. Unique Paths II (Medium)
系列文
從LeetCode學演算法30

1 則留言

0
t19960804
iT邦新手 5 級 ‧ 2020-10-12 11:02:58

版主你好
我想請問一下
空間複雜度為O(1),因為"並沒有需求常數次數以外的空間"
這句話的意思是不是說我們宣告的陣列最壞情況就只會儲存"兩個元素"

Desolve iT邦新手 5 級 ‧ 2020-10-12 11:38:43 檢舉

你好,
是因為最壞狀況下只會儲存兩個元素,這個數量跟資料n的大小完全無關,所以空間複雜度為O(1)。嚴謹一點來說,是因為你的第四句導致第三句的結果,兩者並不等義呦!

我要留言

立即登入留言