Leetcode 169. Majority Element
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
// There is a video on youtube. There are 8 solutions to the problems.
https://www.youtube.com/watch?v=LPIvL-jvGdA
My solution using HashMap
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public int majorityElement(int[] nums) {
HashMap<Integer, Integer> hm = new HashMap();
int len = nums.length;
for (int x : nums) {
int count = 0;
if (hm.containsKey(x)) {
count = hm.get(x);
hm.put(x, count + 1);
} else {
hm.put(x, 1);
}
count = hm.get(x);
if ( count >len / 2) {
return x;
}
}
return 0;
}
}
Boyer-Moore Majority Vote Algorithm
Time complexity: O(n)
Space complexity: O(1)
public class Solution {
public int majorityElement(int[] num) {
int major=num[0], count = 1;
for(int i=1; i<num.length;i++){
if(count==0){
count++;
major=num[i];
}else if(major==num[i]){
count++;
}else count--;
}
return major;
}
}
