Leetcode169. 多数元素

题目描述

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

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

示例 1：

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

示例 2：

1 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;
}