题目描述:
给定一个大小为 n 的整数数组,找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
示例:
输入:[3,2,3] 输出:[3]
题解:
摩尔投票算法:
摩尔投票算法的核心思想是对拼抵消,首先我们考虑最基本的摩尔投票问题,比如找出一组数字序列中出现次数大于总数1/2的数字,易知若该元素存储,则只会存储一个这样的数。假设这个数是nums[0],初始其票数为1,
那么对摩尔投票进行扩展,求大于n/3的所有元素,易知该元素最多有两个,因此我们可以初始化两个element,按和上面一样的流程,最后将出现次数大于n/3的element加入到结果集中即可。
class Solution { public List<Integer> majorityElement(int[] nums) { int element1 = 0; int element2 = 0; int vote1 = 0; int vote2 = 0; for (int num : nums) { if (vote1 > 0 && num == element1) { //如果该元素为第一个元素,则计数加1 vote1++; } else if (vote2 > 0 && num == element2) { //如果该元素为第二个元素,则计数加1 vote2++; } else if (vote1 == 0) { // 选择第一个元素 element1 = num; vote1++; } else if (vote2 == 0) { // 选择第二个元素 element2 = num; vote2++; } else { //如果三个元素均不相同,则相互抵消1次 vote1--; vote2--; } } int cnt1 = 0; int cnt2 = 0; for (int num : nums) { if (vote1 > 0 && num == element1) { cnt1++; } if (vote2 > 0 && num == element2) { cnt2++; } } // 检测元素出现的次数是否满足要求 List<Integer> ans = new ArrayList<>(); if (vote1 > 0 && cnt1 > nums.length / 3) { ans.add(element1); } if (vote2 > 0 && cnt2 > nums.length / 3) { ans.add(element2); } return ans; } }
LeetCode题解及动画演示