### 题目

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.

### 常规做法用HashMap记录频率。计算复杂度：$O(n)$，空间复杂度 $O(n)$

#### 代码

/**
* 使用额外Map记录出现数字的频率
* 计算复杂度：O(n)，空间复杂度O(n)
*/
public class Solution {
public List<Integer> majorityElement(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
for (Integer num : nums) {
Integer freq = map.get(num);
freq = (freq == null)? 1 : freq+1;
map.put(num,freq);
}
List<Integer> result = new ArrayList<>();
Integer target = nums.length / 3;
for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
Integer freq = entry.getValue();
if (freq > target) {
}
}
return result;
}
}


### Boyer-Moore Majority Vote Algorithm

• 如果nums[i] == number1number1的频率count1加一。
• 如果nums[i] == number2number2的频率count2加一。
• 如果nums[i]不等于两个数中的任何一个，
• 如果number1的统计量count1 == 0，用nums[i]替换带子中的number1
• 如果number2的统计量count2 == 0，用nums[i]替换带子中的number2
• 否则，count1count2都减去一。

#### 代码

public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> result = new ArrayList<>();
if (nums.length == 0) { return result; }
int num1 = nums[0], num2 = nums[0], count1 = 0, count2 = 0;
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
if (num == num1) {
count1++;
} else if (num == num2) {
count2++;
} else if (count1 == 0) {
num1 = num; count1 = 1;
} else if (count2 == 0) {
num2 = num; count2 = 1;
} else {
count1--; count2--;
}
}
count1 = 0; count2 = 0;
for (int num : nums) {
if (num == num1) { count1++; continue; }
if (num == num2) { count2++; }
}
int target = nums.length / 3;
if (count1 > target) { result.add(num1); }
if (count2 > target) { result.add(num2); }
return result;
}
}