求众数2

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

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

 

示例 1：

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

输入：nums = [1]
输出：[1]
示例 3：

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

提示：

1 <= nums.length <= 5 * 104
-109 <= nums[i] <= 109
通过次数25,257提交次数56,215

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

摩尔投票

大于三分之一的数是众数时，一个数组中最多有两个众数。

算法思想是设置两个候选人以及两个计数器。

• 遍历到和候选人相同时对应计数器+1
• 当计数器为0时，更换对应的候选人
• 如果和两个候选人都不相同则两个计数器都-1

遍历完剩下的则是2个众数。

最后要对两个候选人进行计数，判断是否大于1/3

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int count1 = 0, count2 = 0;
        int candidate1 = 0, candidate2 = 0;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == candidate1) {
                count1++;
            } else if (nums[i] == candidate2) {
                count2++;
            }else if(count1 == 0){
                candidate1 = nums[i];
                count1++;
            }else if(count2==0){
                candidate2 = nums[i];
                count2++;
            }else{
                count1--;
                count2--;
            }

        }

        count1 = 0;
        count2 = 0;
        int major = nums.length / 3;
        List<Integer> ansList = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == candidate1) {
                count1++;
            } else if (nums[i] == candidate2) {
                count2++;
            }
        }
        if (count1 > major) ansList.add(candidate1);
        if (count2 > major) ansList.add(candidate2);

        return ansList;
    }
}

参考文献

作者：clearboy 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信