Leetcode 169 - Majority Element

題目

Problem#

題目給你一個陣列 nums，回傳出現次數超過 $\lfloor \frac{n}{2} \rfloor$ 的的那個數字(眾數)。

想法#

直覺做就是先建表紀錄每個數字出現的次數，接著排序拿最大即可

較困難的是 follow-up 的 $O(1)$ 空間複雜度，看題解才知道有 Boyer-Moore Majority Vote Algorithm 這個算法

AC Code#

Copy

class Solution2 {
public:
    int majorityElement(vector<int>& nums)
    {
        int n = nums.size();
        unordered_map<int, int> m;
        for(int i : nums)
            m[i]++;
        int mi, mv = INT_MIN;
        for(auto [num, cnt] : m)
        {
            if(cnt > mv)
            {
                mv = cnt;
                mi = num;
            }
        }
        return mi;
    }
};

view raw leetcode/169.cpp delivered with ❤ by emgithub

• 時間複雜度: $\mathcal{O}(n)$
• 空間複雜度: $\mathcal{O}(n)$

---

Copy

class Solution3 {
public:
    int majorityElement(vector<int>& nums)
    {
        int n = nums.size();
        int ans = nums[0], cnt = 1;
        for(int i = 1; i < n; i++)
        {
            if(ans == nums[i])
            {
                cnt++;
            }
            else if(cnt > 0)
            {
                cnt--;
            }
            else
            {
                ans = nums[i];
                cnt = 1;
            }
        }
        return ans;
    }
};

view raw leetcode/169.cpp delivered with ❤ by emgithub

Boyer-Moore Majority Vote Algorithm

• 時間複雜度: $\mathcal{O}(n)$
• 空間複雜度: $\mathcal{O}(1)$

心得#

原始題目很水，follow-up 沒想到QQ