Majority Element II – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
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
C++ Majority Element II LeetCode Solution
class Solution {
public:
vector<int> majorityElement(vector<int>& nums)
{
int sz = nums.size();
int num1 = -1, num2 = -1, count1 = 0, count2 = 0, i;
for (i = 0; i < sz; i++)
{
if (nums[i] == num1)
count1++;
else if (nums[i] == num2)
count2++;
else if (count1 == 0)
{
num1 = nums[i];
count1 = 1;
}
else if (count2 == 0)
{
num2 = nums[i];
count2 = 1;
}
else
{
count1--;
count2--;
}
}
vector<int> ans;
count1 = count2 = 0;
for (i = 0; i < sz; i++)
{
if (nums[i] == num1)
count1++;
else if (nums[i] == num2)
count2++;
}
if (count1 > sz/3)
ans.push_back(num1);
if (count2 > sz/3)
ans.push_back(num2);
return ans;
}
};
Java Majority Element II LeetCode Solution
public List<Integer> majorityElement(int[] nums) {
ArrayList<Integer> res = new ArrayList<Integer>();
if (nums.length==0) return res;
int count[] = new int[2];
int x[] = new int[2];
x[0] = 0; x[1] = 1;
for (int i = 0; i < nums.length; i++) {
if (x[0] == nums[i])
count[0]++;
else if (x[1] == nums[i])
count[1]++;
else if (count[0] == 0) {
x[0] = nums[i];
count[0] = 1;
} else if (count[1] == 0) {
x[1] = nums[i];
count[1] = 1;
} else {
count[0]--;
count[1]--;
}
}
Arrays.fill(count, 0);
for (int i : nums) {// Count again for x1, x2
if (i == x[0]) count[0]++;
else if (i == x[1]) count[1]++;
}
for (int j = 0; j < 2; j++) {
if (count[j] > nums.length/3 && !res.contains(x[j])) res.add(x[j]);
}
return res;
}
Python 3 Majority Element II LeetCode Solution
class Solution:
def majorityElement(self, nums):
count = Counter()
for num in nums:
count[num] += 1
if len(count) == 3:
new_count = Counter()
for elem, freq in count.items():
if freq != 1: new_count[elem] = freq - 1
count = new_count
cands = Counter(num for num in nums if num in count)
return [num for num in cands if cands[num] > len(nums)/3]
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
Leave a comment below
