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

## C++

``````class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> ans;
int candidate1 = 0;
int candidate2 = 1;   // any number different from candidate1
int countSoFar1 = 0;  // # of candidate1 so far
int countSoFar2 = 0;  // # of candidate2 so far

for (const int num : nums)
if (num == candidate1) {
++countSoFar1;
} else if (num == candidate2) {
++countSoFar2;
} else if (countSoFar1 == 0) {  // assign new candidate
candidate1 = num;
++countSoFar1;
} else if (countSoFar2 == 0) {  // assign new candidate
candidate2 = num;
++countSoFar2;
} else {  // meet a new number, so pair out previous counts
--countSoFar1;
--countSoFar2;
}

const int count1 = count(begin(nums), end(nums), candidate1);
const int count2 = count(begin(nums), end(nums), candidate2);

if (count1 > nums.size() / 3)
ans.push_back(candidate1);
if (count2 > nums.size() / 3)
ans.push_back(candidate2);
return ans;
}
};
``````

## JAVA

``````class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> ans = new ArrayList<>();
int candidate1 = 0;
int candidate2 = 1;  // any number different from candidate1
int countSoFar1 = 0; // # of candidate1 so far
int countSoFar2 = 0; // # of candidate2 so far

for (final int num : nums)
if (num == candidate1) {
++countSoFar1;
} else if (num == candidate2) {
++countSoFar2;
} else if (countSoFar1 == 0) { // assign new candidate
candidate1 = num;
++countSoFar1;
} else if (countSoFar2 == 0) { // assign new candidate
candidate2 = num;
++countSoFar2;
} else { // meet a new number, so pair out previous counts
--countSoFar1;
--countSoFar2;
}

int count1 = 0;
int count2 = 0;

for (final int num : nums)
if (num == candidate1)
++count1;
else if (num == candidate2)
++count2;

if (count1 > nums.length / 3)
if (count2 > nums.length / 3)
return ans;
}
}
``````

## Python

``````class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
ans1 = 0
ans2 = 1
count1 = 0
count2 = 0

for num in nums:
if num == ans1:
count1 += 1
elif num == ans2:
count2 += 1
elif count1 == 0:
ans1 = num
count1 = 1
elif count2 == 0:
ans2 = num
count2 = 1
else:
count1 -= 1
count2 -= 1

return [ans for ans in (ans1, ans2) if nums.count(ans) > len(nums) // 3]
``````