Algorithm
Problem Name: 229. Majority Element II
Problem Link: https://leetcode.com/problems/majority-element-ii/
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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int* majorityElement(int* nums, int numsSize, int* returnSize) {
int *r;
int m[2] = { 0 };
int c[2] = { 0 };
int f = 1;
int i, j, x;
*returnSize = 0;
r = malloc(2 * sizeof(int));
if (!r) return NULL;
i = 0;
while (i < numsSize) {
if (m[0] == nums[i]) {
c[0] ++;
} else if (m[1] == nums[i]) {
c[1] ++;
f = 2;
} else if (c[0] == 0) {
m[0] = nums[i];
c[0] = 1;
} else if (c[1] == 0) {
m[1] = nums[i];
c[1] = 1;
f = 2;
} else {
c[0] --;
c[1] --;
}
i ++;
}
j = 0;
while (f > 0) {
f --;
x = 0;
i = 0;
while (i < numsSize) {
if (m[f] == nums[i]) {
x ++;
}
i ++;
}
if (x > numsSize / 3) {
*returnSize += 1;
r[j] = m[f];
j ++;
}
}
return r;
}
Input
nums = [3,2,3]
Output
[3]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int n = nums.size();
vector<int>res;
int c1 = 0, c2 = 0, count1 = 0, count2 = 0;
for (int& x: nums) {
if (x == c1) {
++count1;
} else if (x == c2) {
++count2;
} else if (count1 == 0) {
c1 = x;
++count1;
} else if (count2 == 0) {
c2 = x;
++count2;
} else {
--count1;
--count2;
}
}
count1 = 0;
count2 = 0;
for (int& x: nums) {
if (x == c1) {
++count1;
} else if (x == c2) {
++count2;
}
}
if (count1 > n / 3) {
res.push_back(c1);
}
if (count2 > n / 3) {
res.push_back(c2);
}
return res;
}
};
Input
nums = [3,2,3]
Output
[3]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List majorityElement(int[] nums) {
Integer majorityElementOne = null;
Integer majorityElementTwo = null;
int countOne = 0;
int countTwo = 0;
for (int num : nums) {
if (majorityElementOne != null && num == majorityElementOne) {
countOne++;
} else if (majorityElementTwo != null && num == majorityElementTwo) {
countTwo++;
} else if (countOne == 0) {
majorityElementOne = num;
countOne = 1;
} else if (countTwo == 0) {
majorityElementTwo = num;
countTwo = 1;
} else {
countOne--;
countTwo--;
}
}
List < Integer> result = new ArrayList<>();
countOne = 0;
countTwo = 0;
for (int num : nums) {
if (majorityElementOne != null && majorityElementOne == num) {
countOne++;
}
if (majorityElementTwo != null && majorityElementTwo == num) {
countTwo++;
}
}
if (countOne > nums.length / 3) {
result.add(majorityElementOne);
}
if (countTwo > nums.length / 3) {
result.add(majorityElementTwo);
}
return result;
}
}
Input
nums = [1]
Output
[1]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const majorityElement = function(nums) {
const res = []
const hash = {}
const len = nums.length
const limit = Math.floor(len / 3)
nums.forEach(el => {
if(hash.hasOwnProperty(''+el)) {
hash[el] += 1
} else {
hash[el] = 1
}
})
Object.keys(hash).forEach(el => {
if(hash[el] > limit) res.push(+el)
})
return res
};
Input
nums = [1]
Output
[1]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def majorityElement(self, nums):
c1, c2, cnt1, cnt2 = 0, 1, 0, 0
for num in nums:
if num == c1:
cnt1 += 1
elif num == c2:
cnt2 += 1
elif not cnt1:
c1, cnt1 = num, 1
elif not cnt2:
c2, cnt2 = num, 1
else:
cnt1 -= 1
cnt2 -= 1
return [c for c in (c1, c2) if nums.count(c) > len(nums) // 3]
Input
nums = [1,2]
Output
[1,2]
#6 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0229_MajorityElementII
{
public IList < int> MajorityElement(int[] nums)
{
int count1 = 0, count2 = 0;
int? candidate1 = null, candidate2 = null;
foreach (var num in nums)
{
if (candidate1.HasValue && candidate1 == num)
count1++;
else if (candidate2.HasValue && candidate2 == num)
count2++;
else if (count1 == 0)
{
candidate1 = num;
count1++;
}
else if (count2 == 0)
{
candidate2 = num;
count2++;
}
else
{
count1--;
count2--;
}
}
count1 = count2 = 0;
foreach (var num in nums)
{
if (candidate1 != null && num == candidate1)
count1++;
if (candidate2 != null && num == candidate2)
count2++;
}
var results = new List < int>();
int n = nums.Length;
if (count1 > n / 3)
results.Add(candidate1.Value);
if (count2 > n / 3)
results.Add(candidate2.Value);
return results;
}
}
}
Input
nums = [1,2]
Output
[1,2]