Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Note: The algorithm should run in linear time and in O(1) space.
Example 1:
Input: [3,2,3] Output: [3]Example 2:
Input: [1,1,1,3,3,2,2,2] Output: [1,2]思路：还是用之前的方法，进行投票，首先分析一个为n长数组，元素能大于n/3的，最多只能有两个。然后用上个Majority Element的方法，进行投票，这里有个tricky的地方就是用if else if来进行判断，这样才能保证最后筛选出来的是两个不同的结果。然后这题还需要验证一下，因为有可能找出来的不是majority，跟上题不一样的是，上题保证了有唯一解，这题没有保证，可能找出来的不是，所以最后需要再check一下。然后输出。
class Solution { public List<Integer> majorityElement(int[] nums) { List<Integer> res = new ArrayList<Integer>(); int m = 0; int countm = 0; int n = 0; int countn = 0; for(int a: nums) { if(a == m) { countm++; } else if(a == n) { countn++; } else if(countm == 0) { m = a; countm++; } else if(countn == 0) { n = a; countn++; } else { countm--; countn--; } } countm = 0; countn = 0; for(int i: nums) { if(i == m) { countm++; } else if(i == n) { countn++; } } if(countm > nums.length / 3) { res.add(m); } if(countn > nums.length / 3) { res.add(n); } return res; } }
