Majority Number

Question

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

Analysis

最直观的想法就是,建立HashMap,记录list中的每一个integer元素的个数,如果大于1/2 list长度,即可返回。
进一步分析发现,其实并不需要记录所有的integer元素的个数,可以只记录当前最多的那一个majority。这种方法也称为 wikipedia: Boyer–Moore majority vote algorithm
The Boyer-Moore Vote Algorithm solves the majority vote problem in linear time O(n) and logarithmic space O(log n)
As we sweep we maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0.
When we move the pointer forward over an element e:
  • If the counter is 0, we set the current candidate to e and we set the counter to 1.
  • If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.
When we are done, the current candidate is the majority element, if there is a majority.
换一种角度,是否可以直接从list中读取这个majority呢?如果对list进行排序,那么1/2处的元素,也就是majority的那个integer了。当然这种方法有个问题,就是对于没有majority的情况下(没有一个达到了1/2 总长度),是无法判断是否存在majority的,如果题目中明确一定存在这样的majority,那么这种方法也是可行的。
时间 O(n), 空间 O(1)

Solution

HashMap Solution
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 0;
}
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int listSize = nums.size();
int halfSize = listSize / 2;
int result = 0;
for (int i = 0; i < listSize; i++) {
int num = nums.get(i);
if (!map.containsKey(num)) {
map.put(num, 1);
} else {
map.put(num, 1 + map.get(num));
}
if (map.get(num) > halfSize) {
result = num;
}
}
return result;
}
}
public class Solution {
/**
* @param nums: a array of integers
* @return: find a majority element
*/
public int majorityElement(int[] nums) {
int n = nums.length;
int candidate = nums[0], counter = 0;
for (int i : nums) {
if (counter == 0) {
candidate = i;
counter = 1;
} else if (candidate == i) {
counter++;
} else {
counter--;
}
}
counter = 0;
for (int i : nums) {
if (i == candidate) counter++;
}
if (counter < (n + 1) / 2) return -1;
return candidate;
}
}