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
Solution 1
PythonJavaC++GoC#PHP
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](code-box)
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) {
ans.add(m1);
}
if (n2 > nums.length / 3) {
ans.add(m2);
}
return ans;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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>();
ans.Add(m1);
ans.Add(m2);
return ans.Where(m => nums.Count(n => n == m) > nums.Length / 3).ToList();
}
}(code-box)
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);
}
}(code-box)
