Majority Number
Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it.
Example
Given [1, 1, 1, 1, 2, 2, 2], return 1
Challenge
O(n) time and O(1) extra space
This problem could be solved using Boyer–Moore majority vote algorithm.
public class Solution {
/**
* @param nums: a list of integers
* @return: find a majority number
*/
public int majorityNumber(ArrayList<Integer> nums) {
if (nums == null || nums.size() == 0) {
return -1;
}
int candidate = 0, counter = 0;
for (int i : nums) {
if (counter == 0) {
candidate = i;
counter = 1;
} else if (i == candidate) {
counter++;
} else if (i != candidate) {
counter--;
}
}
return candidate;
}
}
Hope this helps,
Michael