Boyer-Moore Majority Vote Algorithm. Time = O(n), Space = O(1)
http://www.cs.utexas.edu/~moore/best-ideas/mjrty
https://www.youtube.com/watch?v=zOyOwDEF1Rc
Step 1: Find a candidate for majority element
Step 2: Check if this candidate is a majority element
class Solution {
public int majorityElement(int[] nums) {
int majority = 0;
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (count == 0) {
majority = nums[i];
count++;
} else {
if (nums[i] == majority) {
count++;
} else {
count --;
}
}
}
return majority;
}
}
class Solution {
public List<Integer> majorityElement(int[] nums) {
int count1 = 0;
int count2 = 0;
int majority1 = 0;
int majority2 = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == majority1) {
count1++;
} else if (nums[i] == majority2) {
count2++;
} else if (count1 == 0) {
majority1 = nums[i];
count1++;
} else if (count2 == 0) {
majority2 = nums[i];
count2++;
} else {
count1 --;
count2 --;
}
}
count1 = 0;
count2 = 0;
for (int num : nums) {
if (num == majority1) {
count1++;
} else if (num == majority2) {
count2++;
}
}
List<Integer> res = new ArrayList<>();
if (count1 > nums.length / 3) {
res.add(majority1);
}
if (count2 > nums.length / 3) {
res.add(majority2);
}
return res;
}
}