关于我的 Leetcode 题目解答，代码前往 Github：https://github.com/chenxiangcyr/leetcode-answers
169. Majority Element
给定一个无序数组，有 n 个元素，找出其中的一个多数元素，多数元素出现的次数大于⌊ n/2 ⌋。
public int majorityElement(int[] nums) {
/*
Map<Integer, Integer> count = new HashMap<Integer, Integer>();
for(int i : nums) {
int t = count.getOrDefault(i, 0);
t++;
if(t > nums.length / 2) {
return i;
}
count.put(i, t);
}
return 0;
*/
// 多数投票算法 Boyer-Moore Algorithm
int candidate = 0;
int count = 0;
for(int num : nums) {
if(count == 0) {
candidate = num;
}
if(candidate == num) {
count++;
}
else {
count--;
}
}
return candidate;
}
分布式Boyer-Moore
Boyer-Moore还有一个优点，那就是可以使用并行算法实现。相关算法可见Finding the Majority Element in Parallel
其基本思想为对原数组采用分治的方法，把数组划分成很多段(每段大小可以不相同)，在每段中计算出candidate-count二元组，然后得到最终结果。
举个例子，原数组为[1,1,0,1,1,0,1,0,0]
划分1： [1,1,0,1,1] –> (candidate,count)=(1,3)
划分2： [0,1,0,0] –> (candidate,count)=(0,2)
根据(1,3)和(0,2)可得，原数组的多数元素为1.
正因为这个特性，考虑若要从一个非常大的数组中寻找多数元素，数据量可能多大数百G，那么我们甚至可以用MapReduce的方式来解决这个问题。
