Leetcode169. 多数元素

2021年4月26日 268点热度 1人点赞 0条评论

题目描述

给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 $ \lfloor n/2 \rfloor$的元素。

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

示例 1:

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

示例 2:

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

进阶:

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

解题思路

这道题最简单的方法就是哈希法。也就是同一个哈希表去存储每一个元素以及出现的次数,然后返回出现次数大于$ \lfloor n/2 \rfloor$的元素。

这个方法简单易懂,但是时间复杂度为$O(n)$,空间复杂度也为$O(n)$,不符合要求。

如果要把空间复杂度优化到$O(1)$,我们就需要采用非常有名的$Boyer-Moore $投票算法。

摩尔投票法充分利用了题目中的一直条件——数组中一定存在出现次数 大于 $ \lfloor n/2 \rfloor$的元素。那么如果把多数元素记为$+1$,其他元素记为$-1$,那么他们加起来的和肯定大于0 。相反,如果把多数元素记为$-1$,其他元素记为$+1$,那么他们加起来的和肯定小于0。

具体的做法如下:

  • 我们维护一个候选数flagNum和计数器ret。初始时,flagNum可以为任意数,ret为0;
  • 遍历数组nums中的所有元素。首先判断一下计数器ret的状态,如果ret的值变为了0,说明当前的flagNum不是多数元素,用nums[i]去更新flagNum的值。然后,再依据以下规则,更新ret的值:
    • 如果nums[i]flagNum相等,那么ret的值增加1;
    • 如果nums[i]flagNum不等,那么ret的值减少1。
  • 遍历结束后,flagNum即为所求的元素。

时间复杂度:$O(n)$

空间复杂度:$O(1)$

根据摩尔投票法写出的示例代码如下。

示例代码

int majorityElement(vector<int>& nums)
{
    int ret=0;
    int flagNum;
    for(int i=0;i<nums.size();++i)
    {
        if(ret==0)
        {
            flagNum=nums[i];
        }
        if(nums[i]!=flagNum)
        {
            ret--;
        }
        else{
            ret++;
        }
    }
    return flagNum;
}

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论