題目網址：https://leetcode.cn/problems/majority-element/

題意：給一大小為 n 的 array nums, 找出當中個數大於 $⌊ \dfrac{n}{2} ⌋$ 的數字(保證存在一個數滿足此條件)。

進階：試著用 $O(n)$ time, $O(1)$ space 的演算法解決此問題

Solution 1：

想法：利用 hash table 紀錄 {num: count}

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int res = 0, maxCount = 0;
        unordered_map<int, int> umap;

        for (const auto& n : nums) {
            ++umap[n];
            if (umap[n] > maxCount) {
                res = n;
                maxCount = umap[n];
            }
        }
        return res;
    }
};
  • time：$O(n)$ ➔ 遍歷 nums
  • space：$O(n)$ ➔ umap

Solution 2：

想法：利用 Boyer – Moore 投票法

  • 當 res = 0 時, 將 res 設為 nums[i]
  • 否則, 檢查 nums[i] 是否為 res。若是的話 res + 1, 否則 res - 1

考慮特殊 case:

  1. nums = [2,2,1,1,3], 得出 res = 3

    nums[i] 2 2 1 1 3
    cnt 1 2 1 0 1
    res 2 2 2 2 3

  2. nums = [2,2,3,4,5], 得出 res = 5

    nums[i] 2 2 3 4 5
    cnt 1 2 1 0 1
    res 2 2 2 2 5

➔ 以上情況皆不會在本題出現, 因為 2 的個數並沒有 > $⌊ \dfrac{5}{2} ⌋$
➔ 而本題的先決條件就是必有一數的個數 > $⌊ \dfrac{n}{2} ⌋$, 因此 Boyer – Moore 投票法在本題必成立

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int res = 0, cnt = 0;

        for (const auto& n : nums) {
            if (cnt == 0) {
                res = n;
            }
            cnt += (n == res) ? 1 : -1;
        }

        return res;
    }
};
  • time：$O(n)$ ➔ 遍歷 nums
  • space：$O(1)$ ➔ 只需常數空間