摩尔投票

摩尔投票

寻找数组中的多数元素的\(O(1)\)空间复杂度做法。核心思想为不同元素互相抵消。

当然现在存储空间往往不是平静，Hash算法的时间常数更低。

寻找数组中出现概率超过1/2的数

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candi = nums[0];
        int cnt = 0;
        for (int num: nums) {
            if (candi == num) cnt++;
            else if (cnt == 0) candi = num, cnt++;
            else cnt--;
        }
        // problem asserts there always exist a majority number.
        return candi;
        // else we need to check by re-counting:
        // cnt = 0;
        // int th = nums.size() / 2;
        // for(int num: nums) if (candi == num) cnt++;
        // return cnt > th ? candi : -1;
    }
};

寻找数组中出现概率超过1/3的数

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int cnt1 = 0, cnt2 = 0;
        int candi1 = nums[0], candi2 = nums[0];
        for (int num: nums) {
            if (candi1 == num) cnt1++;
            else if (candi2 == num) cnt2++;
            else if (cnt1 == 0) candi1 = num, cnt1++;
            else if (cnt2 == 0) candi2 = num, cnt2++;
            else cnt1--, cnt2--;
        }
        int th = nums.size() / 3;
        vector<int> ans;
        // recounting
        cnt1 = cnt2 = 0;
        for (int num: nums) {
            if (num == candi1) cnt1++;
            else if (num == candi2) cnt2++;
        }
        if (cnt1 > th) ans.push_back(candi1);
        if (cnt2 > th) ans.push_back(candi2);
        return ans;
    }
};