求众数2

229. 求众数 II

难度中等443

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

示例 1：

输入：[3,2,3]
输出：[3]

示例 2：

输入：nums = [1]
输出：[1]

示例 3：

输入：[1,1,1,3,3,2,2,2]
输出：[1,2]

提示：

• 1 <= nums.length <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。

摩尔投票

求数量大于 n/3下取整的数组元素，由题意可知，结果最多有两个数字。

使用两个变量维护元素，两个变量维护计数器。

• 如果第一个计数器大于0遍历到的元素和第一个元素相同，那么第一个计数器自增

• 如果第二个计数器大于0遍历到的元素和第二个元素相同，那么第二个计数器自增

• 如果第一个计数器等于0，那么设置当前的数字为element1

• 如果第二个计数器等于0，那么设置当前的数字为element2

• 如果遍历到的元素和第一个第二个都不相同，那么两个计数器都自减

class Solution {
    public List<Integer> majorityElement(int[] nums) {    
        List<Integer> ans = new ArrayList<>();
        int n = nums.length;
        
        int element1=0,element2=0;
        int vote1=0,vote2=0;

        for(int i=0;i<n;i++){
            if(vote1>0 && nums[i]==element1){
                vote1++;
            }else if(vote2>0 && nums[i]==element2){
                vote2++;
            }else if(vote1==0){
                element1 = nums[i];
                vote1++;
            }else if(vote2==0){
                element2 = nums[i];
                vote2++;
            }else{
                vote1--;
                vote2--;
            }
        }

        int cnt1=0,cnt2=0;
        for(int i=0;i<n;i++){
            if(nums[i]==element1){
                cnt1++;
            }else if(nums[i]==element2){
                cnt2++;
            }
        }
        
        if(cnt1*3 > n) ans.add(element1);
        if(cnt2*3 > n) ans.add(element2);

        return ans;
    }
}

赏

谢谢你请我吃糖果

微信