[leetcode]229. Majority Element II

Problem

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Code

class Solution {
public:
    vector majorityElement(vector& nums) {
        int cnt1 = 0;
        int cnt2 = 0;
        int p1 = 0;
        int p2 = 0;
        int n = nums.size();
        for (int i = 0;i < n;i ++) {
            if (nums[i] == p1 || nums[i] == p2) {
                if (nums[i] == p1) cnt1 ++;
                if (nums[i] == p2) cnt2 ++;
            }
            else if (cnt1 == 0 || cnt2 == 0) {
                if (cnt1 == 0) {
                    cnt1 ++;
                    p1 = nums[i];
                }
                else {
                    cnt2 ++;
                    p2 = nums[i];
                }
            }
            else  {
                cnt1 --;
                cnt2 --;
            }
        }
    
    
        int a1 = 0;
        int a2 = 0;
        for (int i = 0;i < n;i ++) {
            if (nums[i] == p1) a1 ++;
            if (nums[i] == p2) a2 ++;
        }
        vector ans;
        if (a1 > n / 3) ans.push_back(p1);
        if (a2 > n / 3 && p1 != p2) ans.push_back(p2);
        return ans;
    }
};