# 229. Majority Element II

## Description

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Example 1:

Input: nums = [3,2,3]
Output: [3]


Example 2:

Input: nums = [1]
Output: [1]


Example 3:

Input: nums = [1,2]
Output: [1,2]


Constraints:

• 1 <= nums.length <= 5 * 104
• -109 <= nums[i] <= 109

Follow up: Could you solve the problem in linear time and in O(1) space?

## Solutions

• class Solution {
public List<Integer> majorityElement(int[] nums) {
int n1 = 0, n2 = 0;
int m1 = 0, m2 = 1;
for (int m : nums) {
if (m == m1) {
++n1;
} else if (m == m2) {
++n2;
} else if (n1 == 0) {
m1 = m;
++n1;
} else if (n2 == 0) {
m2 = m;
++n2;
} else {
--n1;
--n2;
}
}
List<Integer> ans = new ArrayList<>();
n1 = 0;
n2 = 0;
for (int m : nums) {
if (m == m1) {
++n1;
} else if (m == m2) {
++n2;
}
}
if (n1 > nums.length / 3) {
}
if (n2 > nums.length / 3) {
}
return ans;
}
}

• class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int n1 = 0, n2 = 0;
int m1 = 0, m2 = 1;
for (int m : nums) {
if (m == m1)
++n1;
else if (m == m2)
++n2;
else if (n1 == 0) {
m1 = m;
++n1;
} else if (n2 == 0) {
m2 = m;
++n2;
} else {
--n1;
--n2;
}
}
vector<int> ans;
if (count(nums.begin(), nums.end(), m1) > nums.size() / 3) ans.push_back(m1);
if (count(nums.begin(), nums.end(), m2) > nums.size() / 3) ans.push_back(m2);
return ans;
}
};

• class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
n1 = n2 = 0
m1, m2 = 0, 1
for m in nums:
if m == m1:
n1 += 1
elif m == m2:
n2 += 1
elif n1 == 0:
m1, n1 = m, 1
elif n2 == 0:
m2, n2 = m, 1
else:
n1, n2 = n1 - 1, n2 - 1
return [m for m in [m1, m2] if nums.count(m) > len(nums) // 3]


• func majorityElement(nums []int) []int {
var n1, n2 int
m1, m2 := 0, 1
for _, m := range nums {
if m == m1 {
n1++
} else if m == m2 {
n2++
} else if n1 == 0 {
m1, n1 = m, 1
} else if n2 == 0 {
m2, n2 = m, 1
} else {
n1, n2 = n1-1, n2-1
}
}
n1, n2 = 0, 0
for _, m := range nums {
if m == m1 {
n1++
} else if m == m2 {
n2++
}
}
var ans []int
if n1 > len(nums)/3 {
ans = append(ans, m1)
}
if n2 > len(nums)/3 {
ans = append(ans, m2)
}
return ans
}

• class Solution {
/**
* @param Integer[] $nums * @return Integer[] */ function majorityElement($nums) {
$rs = [];$n = count($nums); for ($i = 0; $i <$n; $i++) {$hashmap[$nums[$i]] += 1;
if ($hashmap[$nums[$i]] >$n / 3) {
array_push($rs,$nums[$i]); } } return array_unique($rs);
}
}

• public class Solution {
public IList<int> MajorityElement(int[] nums) {
int n1 = 0, n2 = 0;
int m1 = 0, m2 = 1;
foreach (int m in nums)
{
if (m == m1)
{
++n1;
}
else if (m == m2)
{
++n2;
}
else if (n1 == 0)
{
m1 = m;
++n1;
}
else if (n2 == 0)
{
m2 = m;
++n2;
}
else
{
--n1;
--n2;
}
}
var ans = new List<int>();