<p>Given an integer array of size <code>n</code>, find all elements that appear more than <code>&lfloor; n/3 &rfloor;</code> times.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,2,3]
<strong>Output:</strong> [3]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1]
<strong>Output:</strong> [1]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2]
<strong>Output:</strong> [1,2]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong> Could you solve the problem in linear time and in <code>O(1)</code> space?</p>

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int n = nums.size();
        int c1 = 0, c2 = 0;
        int ele1, ele2;

        for(int i=0; i<n; i++) {
            if(c1 == 0 && ele2 != nums[i]) {
                c1 = 1;
                ele1 = nums[i];
            }
            else if(c2 == 0 && ele1 != nums[i]) {
                c2 = 1;
                ele2 = nums[i];
            }
            else if(ele1 == nums[i])
                c1++;
            else if(ele2 == nums[i])
                c2++;
            else {
                c1--;
                c2--;
            }
        }

        int maj1 = 0, maj2 = 0;
        for(int i=0; i<n; i++) {
            if(nums[i] == ele1) maj1++;
            if(nums[i] == ele2) maj2++;
        }

        if(maj1 > n/3 && maj2 > n/3) return {ele1, ele2};
        if(maj1 > n/3) return {ele1};
        if(maj2 > n/3) return {ele2};

        return {};
    }
};
18400