题目：
给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
说明: 要求算法的时间复杂度为O(n)，空间复杂度为O(1)。
示例 1:
输入: [3,2,3]
输出: [3]
示例 2:
输入: [1,1,1,3,3,2,2,2]
输出: [1,2]
答案：
class Solution {
// 众数求解算法
public List<Integer> majorityElement(int[] nums) {
// 返回结果集
List<Integer> result = new ArrayList<>();
// 黑板(用于记录数据用)
LinkedHashMap<Integer, Integer> blackboard = new LinkedHashMap<>();
// 左边记录到的位置
int leftPs = 0;
// 右边记录到的位置
int rightPs = nums.length - 1;
while (leftPs <= rightPs) {
for (int i = leftPs; i <= rightPs; i++) {
if (blackboard.get(nums[i]) == null) {
blackboard.put(nums[i], 1);
if (leftPs > rightPs || 1>nums.length/3) {
result.add(nums[i]);
}
leftPs = i + 1;
break;
} else {
int count = blackboard.get(nums[i]);
count++;
if (!result.contains(nums[i]) && count>nums.length/3) {
result.add(nums[i]);
}
blackboard.put(nums[i], count);
leftPs = i + 1;
}
}
for (int i = rightPs; i >= leftPs; i--) {
if (blackboard.get(nums[i]) == null) {
blackboard.put(nums[i], 1);
if (rightPs < leftPs || 1>nums.length/3) {
result.add(nums[i]);
}
rightPs = i - 1;
break;
} else {
int count = blackboard.get(nums[i]);
count++;
if (!result.contains(nums[i]) && count>nums.length/3) {
result.add(nums[i]);
}
blackboard.put(nums[i], count);
rightPs = i - 1;
}
}
}
return result;
}
}