LeetCode Problem
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.
Solution
In our solution, we use a simple iteration to count the appear times of each element.
C# Solution
Solution1 – simple iteration
public class Solution {
public int MajorityElement(int[] nums) {
if(nums.Length == 1)
{
return nums[0];
}
//key corresponds to the int element, value corresponds to the count times
Dictionary<int, int> dict = new Dictionary<int, int>();
int tmp = 0;
int check = nums.Length/2;
foreach(int num in nums)
{
if(dict.ContainsKey(num)) //check if dict contains the int element
{
tmp = dict[num]+1;
if(tmp>check)
{
return num;
}
dict[num] = tmp;
}
else
{
dict.Add(num,1);
}
}
return -1;
}
}Solution2 – the shortest solution
public class Solution {
public int MajorityElement(int[] nums) {
Array.Sort(nums);
return(nums[nums.Length/2]);
}
}Time Complexity : O(n logn)
The second solution, we sort the array first, and find the middle element of it.
That is because if an element appears more than ⌊n / 2⌋ times, and the array after sort, than no matter what number is it, we may find it at the index – [nums.Length/2]
⭐Solution3 – Boyer-Moore Voting Algorithm (*1)
public class Solution {
public int MajorityElement(int[] nums) {
int majorNum = 0;
int cnt = 0;
foreach(int num in nums)
{
if(cnt == 0)
{
majorNum = num;
}
cnt += majorNum == num ? 1 : -1;
}
return majorNum;
}
}Time Complexity : O(n)
Java Solution
❌Solution1 – not recommend, too slow
class Solution {
public int majorityElement(int[] nums) {
if(nums.length == 1)
{
return nums[0];
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int tmp = 0;
int check = nums.length/2;
for(int num : nums)
{
if(map.containsKey(num))
{
tmp = map.get(num)+1;
if(tmp>check)
{
return num;
}
map.put(num, tmp);
}
else
{
map.put(num, 1);
}
}
return -1;
}
}❌Solution1.1 – not recommend, that’s to slow, just a little practice of sorting Java map by value
class Solution {
public int majorityElement(int[] nums) {
if(nums.length == 1)
{
return nums[0];
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int tmp = 0;
int check = nums.length/2;
//1. init
for(int num : nums)
{
if(map.containsKey(num))
{
tmp = map.get(num)+1;
map.put(num, tmp);
}
else
{
map.put(num, 1);
}
}
//2.sort map by value and find the last element's key
Map.Entry<Integer,Integer> sorted =
map.entrySet().stream()
.sorted(Map.Entry.comparingByValue())
.skip(map.size()-1).findFirst().get();
return sorted.getKey();
}
}In this solution, we remove the check of each iteration, and just sorted the map by value and get the last key.
Solution1.2
class Solution {
public int majorityElement(int[] nums) {
if(nums.length == 1)
{
return nums[0];
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int check = nums.length/2;
//1. init
for(int num : nums)
{
if(map.containsKey(num))
{
map.put(num, map.get(num)+1);
}
else
{
map.put(num, 1);
}
}
//2.for check
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if(entry.getValue()>check)
{
return entry.getKey();
}
}
return -1;
}
}Solution2
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return(nums[nums.length/2]);
}
}⭐Solution3 – Boyer-Moore Voting Algorithm
class Solution {
public int majorityElement(int[] nums) {
int majorNum = 0;
int cnt = 0;
for(int num : nums)
{
if(cnt == 0)
{
majorNum = num;
}
cnt += majorNum == num ? 1 : -1;
}
return majorNum;
}
}Python3 Solution
Solution1 – dict with easy for loop
class Solution:
def majorityElement(self, nums: List[int]) -> int:
mid = (int)(len(nums)/2)
#init dictionary
d = {} #dict
for num in nums:
if(num in d):
d[num] = d[num]+1
else:
d[num] = 1
for i in d:
if(d[i]>mid):
return i
return -1;Solution1.1 – dict with sort
class Solution:
def majorityElement(self, nums: List[int]) -> int:
mid = (int)(len(nums)/2)
#init dictionary
d = {} #dict
for num in nums:
if(num in d):
d[num] = d[num]+1
else:
d[num] = 1
d = dict(sorted(d.items(), key=lambda item: item[1], reverse=True))
return list(d.keys())[0]Solution2
class Solution:
def majorityElement(self, nums: List[int]) -> int:
nums.sort();
return nums[(int)(len(nums)/2)]⭐Solution3 – Boyer-Moore Voting Algorithm
class Solution:
def majorityElement(self, nums: List[int]) -> int:
majorNum = 0
cnt = 0
for num in nums:
if cnt == 0:
majorNum = num
cnt += 1 if majorNum == num else -1
return majorNumConclusion
🧡If my solution helps, that is my honor!
🧡You can support me by clicking some ad, Thanks a lot
✅If you got any problem about the explanation or you need other programming language solution, please feel free to let me know (either leave a comment or contact me by Messenger is ok!)
The problem link : Majority Element – LeetCode
Reference
- java – Sort a Map<Key, Value> by values – Stack Overflow
- Boyer–Moore majority vote algorithm – Wikipedia
Latest Post
- LeetCode #506 Relative Ranks Solution & Explanation
- LeetCode #292 Nim Game Solution & Explanation
- LeetCode #881 Boats to Save People Solution & Explanation
- LeetCode #2441 Largest Positive Integer That Exists With Its Negative Solution & Explanation
- LeetCode #2000 Reverse Prefix of Word Solution & Explanation