题目：
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.
链接： http://leetcode.com/problems/majority-element-ii/
题解：
依然是Boyer-Morrer Voting Algorithm。这回我们要设置两个变量来进行voting。
Time Complexity - O(n)， Space Complexity - O(1)。
public class Solution { public List<Integer> majorityElement(int[] nums) { List<Integer> res = new ArrayList<>(); if(nums == null || nums.length == 0) return res; int candidate1 = 0, candidate2 = 0, count1 = 0, count2 = 0; for(int i : nums) { if(i == candidate1) count1++; else if(i == candidate2) count2++; else if(count1 == 0) { candidate1 = i; count1 = 1; } else if (count2 == 0) { candidate2 = i; count2 = 1; } else { count1--; count2--; } } count1 = 0; count2 = 0; for(int i : nums) { if(i == candidate1) count1++; else if(i == candidate2) count2++; } if(count1 > nums.length / 3) res.add(candidate1); if(count2 > nums.length /3) res.add(candidate2); return res; } }
Reference:
https://leetcode.com/discuss/42768/o-n-time-o-1-space
https://leetcode.com/discuss/49596/clear-o-n-solution-in-python-no-data-structure-or-sort
https://leetcode.com/discuss/46560/boyer-moore-method-java-implementation
https://leetcode.com/discuss/56737/my-o-n-time-solution-20ms
https://leetcode.com/discuss/43580/my-c-solution
https://leetcode.com/discuss/48238/c%23-solution-with-o-n-time-and-o-1-space-via-improved-quick-sort
https://leetcode.com/discuss/42806/boyer-moore-majority-vote-algorithm-generalization
https://leetcode.com/discuss/43248/boyer-moore-majority-vote-algorithm-and-my-elaboration
原文：http://www.cnblogs.com/yrbbest/p/4997354.html