《leetcode》169. 多数元素 229. 求众数 II《摩尔投票》

最新推荐文章于 2024-08-09 10:07:56 发布

Zyy~

最新推荐文章于 2024-08-09 10:07:56 发布

阅读量153

点赞数

分类专栏： leetcode 文章标签： leetcode 算法

本文链接：https://blog.csdn.net/Look_star/article/details/116017190

版权

leetcode 专栏收录该内容

48 篇文章

订阅专栏

本文介绍了如何使用摩尔投票法在O(n)时间内找出数组中出现次数大于n/2的多数元素，以及如何进一步处理找出所有出现次数超过n/3的众数。通过实例和代码展示了两种算法的实现和应用。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

169. 多数元素

难度简单963

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

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

示例 2：

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

进阶：

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

Code：

class Solution {
    //摩尔投票法：先假设第一个数过半数并设cnt=1；遍历后面的数如果相同则cnt+1，不同则减一，当cnt为0时则更换新的数字为候选数（成立前提：有出现次数大于n/2的数存在）
    // 核心就是对拼消耗
    public int majorityElement(int[] nums) {
        int ans=nums[0];
        int count=1;
        for(int i=1;i<nums.length;i++)
        {
            if(count==0)
                ans=nums[i];
            count+=ans==nums[i]?1:-1;
        }
        return ans;
    }
}

229. 求众数 II

难度中等358

给定一个大小为 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

解题思路：

Code：

class Solution {
    //摩尔投票 O(n) O(1)
    public List<Integer> majorityElement(int[] nums) {
        List<Integer>re=new ArrayList<Integer>();
        if(nums.length<1) return re;
        int candiate1=nums[0];
        int candiate2=nums[0];
        int count1=0,count2=0;
        for(int i=0;i<nums.length;i++)
        {
            if(candiate1==nums[i])
            {
                count1++;
                continue;
            }
            if(candiate2==nums[i])
            {
                count2++;
                continue;
            }
            if(count1==0)
            {
                candiate1=nums[i];
                count1++;
                continue;
            }
            if(count2==0)
            {
                candiate2=nums[i];
                count2++;
                continue;
            }
            count1--;
            count2--;
        }
        count1=0;
        count2=0;
        for(int i=0;i<nums.length;i++)
        {
            if(candiate1==nums[i])
            {
                count1++;
                continue;
            }
            if(candiate2==nums[i])
            {
                count2++;
            }
        }
        if(count1>nums.length/3)
            re.add(candiate1);
        if(count2>nums.length/3)
            re.add(candiate2);
        return re;
    }
}