229. Majority Element II

题目：

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/

7/24/2017

自己不会做，参考别人的

步骤，因为找more than n/3，所以最多有2个答案。

1. 先找到candidate1, candidate2，通过2个count来找，目标是找到出现频率最高的2个数，或者是最高频和次高频出现的第一个数。这里的count其实是相对的出现次数。

2. 重新找到这2个candidate的实际出现次数

3. 与n/3来比较，看是否加入到结果中去。

Boyer-Morrer Voting Algorithm，看别人的总结：

假如给定一个数组，要求majority elements，这些elements出现 > 数组的theta (比如theta = 0.3， 0.4，0.5)。方法应该是如下: Time Complexity - O(n)， Space Complexity - O(1 / theta)。

1) 建立一个k个数的map，比如more than [1/2]则 k = 1， more than [1/3]则 k = 2， more than [1/4]则 k = 3。

2) 当map.size() > k时，对map中每个元素进行count--，移除 = 0元素

3) 对map中剩余元素进行count++

4）最后输出map中count > theta * n的元素。

 1 public class Solution {
 2     public List<Integer> majorityElement(int[] nums) {
 3         List<Integer> result = new ArrayList<Integer>();
 4         if (nums == null || nums.length == 0) {
 5             return result;
 6         }
 7         int candidate1 = 0, candidate2 = 0, count1 = 0, count2 = 0;
 8         for (int num: nums) {
 9             if (num == candidate1) {
10                 count1++;
11             } else if (num == candidate2) {
12                 count2++;
13             } else if (count1 == 0) {
14                 candidate1 = num;
15                 count1++;
16             } else if (count2 == 0) {
17                 candidate2 = num;
18                 count2++;
19             } else {
20                 count1--;
21                 count2--;
22             }
23         }
24         count1 = 0;
25         count2 = 0;
26         
27         for (int num: nums) {
28             if (num == candidate1) {
29                 count1++;
30             } else if (num == candidate2) {
31                 count2++;
32             }
33         }
34         if (count1 > nums.length / 3) {
35             result.add(candidate1);
36         }
37         if (count2 > nums.length / 3) {
38             result.add(candidate2);
39         }        
40         return result;
41     }
42 }

参考

https://gregable.com/2013/10/majority-vote-algorithm-find-majority.html

http://www.cnblogs.com/yrbbest/p/4997354.html

http://www.cnblogs.com/yrbbest/p/4491637.html

别人的答案

https://discuss.leetcode.com/topic/17564/boyer-moore-majority-vote-algorithm-and-my-elaboration

https://discuss.leetcode.com/topic/32510/java-easy-version-to-understand

更加一般化，python

https://discuss.leetcode.com/topic/17409/6-lines-general-case-o-n-time-and-o-k-space