在做leetcode的这道题 229. Majority Element II 时发现了这个有趣的问题。
Boyer-Moore 算法
对于这类问题，在此博客中有详细的介绍，我再用中文简述一下。
就是从一个无序的数组中，找出一个出现次数超过1/2数组长度的元素。很容易分析出，这样的元素最多存在一个。如果先使用排序再统计，则很容易就可以得到这个元素，但这样做的时间复杂度为nlog(n)。而 Boyer-Moore 算法可以做到O(n)的时间复杂度以及O(1)的空间开销。
其具体思路如下：
先做一次数组遍历，在此过程中维护两个变量number, count。如果当前元素与number相同，则count加1，否则减1。如果count为0，则将number替换为当前的元素。当遍历一般之后，很容易分析出，如果存在多数元素，则最后维护的number肯定是这个数字。
再遍历一般，验证当前number的频率是否超过1/2。
在博客中给出的python代码如下：
candidate = 0
count = 0
for value in input:
if count == 0:
candidate = value
if candidate == value:
count += 1
else:
count -= 1
leetcode的题目
题目描述如下：
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
要求是找超过⌊ n/3 ⌋的元素，则这样的元素最多会有2个，其实现思路与之前的相同，区别在于遍历时维护两个数字，这其中其实也存在一些小的trick，请看代码细细品味 : )。
实现代码如下：
public List<Integer> majorityElement(int[] nums) {
List<Integer> result = new ArrayList<>();
if(nums==null || nums.length==0)
return result;
int number1 = nums[0], number2 = nums[0], count1 = 0, count2 = 0;
for(int i=0; i<nums.length; i++){
if(nums[i]==number1)
count1++;
else if(nums[i]==number2)
count2++;
else if(count1==0){
number1=nums[i];
count1=1;
}
else if(count2==0){
number2=nums[i];
count2=1;
}
else{
count1--;
count2--;
}
}
count1=0;
count2=0;
for(int i=0; i<nums.length; i++){
if(nums[i]==number1)
count1++;
else if(nums[i]==number2)
count2++;
}
if(count1>nums.length/3)
result.add(number1);
if(count2>nums.length/3)
result.add(number2);
return result;
}