|
给定一个大小为n的整数数组，找出其中所有出现超过⌊n/3⌋次的元素。 示例 1：
示例 2： 示例 3： 输入：[1,1,1,3,3,2,2,2] 输出：[1,2]
提示： 1<=nums.length<=5*10^4 -10^9<=nums[i]<=10^9
这题说的是找出数组中出现次数超过[n/3]的元素，最简单的一种方式就是先使用map统计每个数字出现的次数，然后再找出出现次数大于[n/3]的元素，原理比较简单，我们来看下代码 public List<Integer> majorityElement(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
//先统计每个元素出现的次数
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
List<Integer> res = new ArrayList<>();
int threshold = nums.length / 3;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
//查找出现次数大于[ n/3 ] 次的元素。
if (entry.getValue() > threshold) {
res.add(entry.getKey());
//优化
//出现次数大于[ n/3 ] 次的元素最多有2个，
//当出现两个的时候就不需要在找了
if (res.size() == 2)
return res;
}
}
return res;
}
在前面我们做过579，摩尔投票算法解主要元素，他是找出出现次数大于[n/2]的元素。而这题是找出出现次数大于[n/3]的元素。我们可以把它想象成为一个游戏，就是开心消消乐。 
游戏中是同一方向上每3个相同的可以同时销毁。这题我们可以假设每3个不同的数字可以同时销毁。如果某个数出现超过[ n/3 ]次，那么最后销毁的时候他肯定是剩下的。
因为需要超过[ n/3 ]次，所以剩下的最多只能有两个。我们使用两个变量记录这两个数字，最后这两个数字出现次数究竟有没有超过[ n/3 ]次，我们还需要在判断。
public List<Integer> majorityElement(int[] nums) {
int numA = Integer.MAX_VALUE;
int numB = Integer.MAX_VALUE;
int countA = 0;
int countB = 0;
for (int num : nums) {
if (num == numA) {
countA++;//统计A的个数
} else if (num == numB) {
countB++;//统计B的个数
} else if (countA == 0) {
numA = num;//A还没有，给他赋值
countA = 1;
} else if (countB == 0) {
numB = num;//B还没有，给他赋值
countB = 1;
} else {
//到这里说明A和B都有了，并且这里出现了
//一个不是A或B的值。
//只有出现3个不同数字的时候，他们
//才能同时销毁
countA--;
countB--;
}
}
//需要再次统计numA和numB的个数，确定是否大于[ n/3 ]
countA = 0;
countB = 0;
for (int num : nums) {
if (num == numA)
countA++;
else if (num == numB)
countB++;
}
List<Integer> res = new ArrayList<>();
//如果A出现的次数大于[ n/3 ]，就把他放到集合res中
if (countA > nums.length / 3)
res.add(numA);
//如果B出现的次数大于[ n/3 ]，就把他放到集合res中
if (countB > nums.length / 3)
res.add(numB);
return res;
}
提醒：游戏虽好，可不要贪玩哦！
|
