LC 169. Majority Element

https://leetcode.com/problems/majority-element/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int cnt = 0;
        int candidate = 0;
        for (auto &x: nums) {
            if (cnt == 0) {
                candidate = x;
            }
            if (candidate == x) cnt += 1;
            else cnt -= 1;
        }
        return candidate;
    }
};

Time Complexity: O(n)
Space: O(1)

是一題很好的面試題，可以做到最後的 space O(1) 的好題目，最好把這個奇怪的魔法記起來