Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 229. Majority Element II

---

題目：


解答：

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int cnt1 = 0;
        int cnt2 = 0;
        int can1 = 0;
        int can2 = 1;

        for (int n : nums) {
            if (n == can1) {
                cnt1 += 1;
            }
            else if (n == can2) {
                cnt2 += 1;
            }
            else if (cnt1 == 0) {
                can1 = n;
                cnt1 = 1;
            }
            else if (cnt2 == 0) {
                can2 = n;
                cnt2 = 1;
            }
            else {
                cnt1 -= 1;
                cnt2 -= 1;
            }
        }

        cnt1 = 0;
        cnt2 = 0;
        for (int n : nums) {
            if (n == can1) {
                cnt1 += 1;
            }
            else if (n == can2) {
                cnt2 += 1;
            }
        }

        vector<int> ans;
        if (cnt1 > nums.size() / 3) {
            ans.push_back(can1);
        }
        if (cnt2 > nums.size() / 3) {
            ans.push_back(can2);
        }

        return ans;
    }
};