169. Majority Element - Easy

前往題目

之前寫的文章

想法

• 排序後中間的一定是最多的
• 或是用hashmap存，然後每次都更新最大值，這樣比排序快一點，因為只要O(n)，但空間也需要O(n)

思路

這題的關鍵是Boyer–Moore majority vote algorithm(摩爾投票算法)，這種人家研究出來發表的算法只能直接死背了，根本不可能自己想出來😂

1. 疊代整個陣列，維護count和candidate
2. 只要count == 0的時候就換一個candidate，否則遇到跟candidate不一樣的數字就把count - 1，遇到一樣就+1這是因為把同意它的與不同意的都列入考量，因為同意的人比較多，這樣兩兩消去最後只會剩下最多同意的人，可以參考這篇文章

Code

class Solution {
    public int majorityElement(int[] nums) {
        // Boyer–Moore majority vote algorithm(摩爾投票算法)

        int cand = 0; // Candidate of majority element
        int count = 0; // Counter of candidate of majority element

        // Iterate the array
        for (int i = 0; i < nums.length; ++i) {
            // Assign new candidate
            if (count == 0) {
                cand = nums[i];
                ++count;
            } else if (nums[i] != cand) {
                --count;
            } else {
                ++count;
            }
        }
        return cand;
    }
}

2024/05/10

• 忘了這個投票演算法，所以用sort然後直接回傳中間值解決😂，雖然accepted但是是O(nlogn)，投票演算法只需要O(n)時間