Majority Element – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Example 1:
Input: nums = [3,2,3] Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2] Output: 2
Constraints:
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109
C++ Majority Element LeetCode Solution
class Solution {
public:
int majorityElement(vector<int>& nums) {
return majority(nums, 0, nums.size() - 1);
}
private:
int majority(vector<int>& nums, int l, int r) {
if (l == r) {
return nums[l];
}
int m = l + (r - l) / 2, lm = majority(nums, l, m), rm = majority(nums, m + 1, r);
if (lm == rm) {
return lm;
}
return count(nums.begin() + l, nums.begin() + r + 1, lm) > count(nums.begin() + l, nums.begin() + r + 1, rm) ? lm : rm;
}
};
Java Majority Element LeetCode Solution
// Sorting
public int majorityElement1(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
// Hashtable
public int majorityElement2(int[] nums) {
Map<Integer, Integer> myMap = new HashMap<Integer, Integer>();
//Hashtable<Integer, Integer> myMap = new Hashtable<Integer, Integer>();
int ret=0;
for (int num: nums) {
if (!myMap.containsKey(num))
myMap.put(num, 1);
else
myMap.put(num, myMap.get(num)+1);
if (myMap.get(num)>nums.length/2) {
ret = num;
break;
}
}
return ret;
}
// Moore voting algorithm
public int majorityElement3(int[] nums) {
int count=0, ret = 0;
for (int num: nums) {
if (count==0)
ret = num;
if (num!=ret)
count--;
else
count++;
}
return ret;
}
// Bit manipulation
public int majorityElement(int[] nums) {
int[] bit = new int[32];
for (int num: nums)
for (int i=0; i<32; i++)
if ((num>>(31-i) & 1) == 1)
bit[i]++;
int ret=0;
for (int i=0; i<32; i++) {
bit[i]=bit[i]>nums.length/2?1:0;
ret += bit[i]*(1<<(31-i));
}
return ret;
}
Python 3 Majority Element LeetCode Solution
class Solution(object):
def majorityElement1(self, nums):
nums.sort()
return nums[len(nums)//2]
def majorityElement2(self, nums):
m = {}
for n in nums:
m[n] = m.get(n, 0) + 1
if m[n] > len(nums)//2:
return n
def majorityElement(self, nums):
candidate, count = nums[0], 0
for num in nums:
if num == candidate:
count += 1
elif count == 0:
candidate, count = num, 1
else:
count -= 1
return candidate
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
Related posts:
Remove Element – LeetCode Solution
Find First and Last Position of Element in Sorted Array – LeetCode Solution
Find Peak Element – LeetCode Solution
Two Sum- LeetCode Solution
Construct Binary Tree from Preorder and Inorder Traversal – LeetCode Solution
Find Minimum in Rotated Sorted Array – LeetCode Solution
