Sitch's Blog
0%

LeetCode_剑指Offer No.39

发表于 分类于 Valine：

求数组中的众数

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

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

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2

限制：

1 <= 数组长度 <= 50000

题目分析

题目关键词：出现次数，即我们很容易想到对次数进行统计然后查找的暴力方式，当然，没有介绍的必要。

另一个关键词：超过一半，超过一半的性质能带给我们什么优势？暴力法没有顾及到，下面介绍的抵消法/摩尔投票法则利用了这一性质进行提速。

再仔细思考题目性质：

核心性质————寻找众数，众数次数超过一半————众数次数 - 所有其他数字加起来出现的次数 0

  1. 我们可以拿出一个 众数，和 一个非众数 匹配抵消。两两抵消后，最终剩下的肯定是众数。

  2. 假设当前数是a，碰到下一个不同的数b，a和b抵消后，不管a b 和众数是什么关系。之后的数组中依然有性质————众数次数 - 所有其他数字加起来出现的次数 0 ，即a和b的抵消不影响我们在后续数组中找众数。

  3. 即我们可以按序把两两不相同的数抵消，相同的数累计起来去抵消后续不同的数。并且后续的数组中依然可以继续抵消。

  4. 这样即可递归下去，最终遍历完整个数组，把所有数抵消了一遍，我们得到剩下的数remain=众数。

算法流程

  1. 取第一个数作为当前remain

  2. 遍历到下一个数

    • 假如不同，则两两抵消，由上面分析可知，不影响后面数组中最后留下的是众数。
    • 假如相同，则在count中累计起来，后面可以抵消更多的不同的数。

  3. 遍历完一整遍数组，全部抵消完毕，则最后remain保持为抵消后多余出来的众数

题解代码

抵消法做法很简单，值得注意的是理解算法的正确性，为什么这样做是对的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int majorityElement(vector<int& nums) 
    {
        //抵消思路，因为次数超过一半————众数次数 - 所有其他数字加起来出现的次数 0 ,
        //即取 众数一次 抵消 非众数一次 最终剩下来的就是众数
        //即 假设a是众数，碰到下个数不是a， 那么这两个数抵消，剩下的数组里依然有 众数次数 - 所有其他数字加起来出现的次数 0
        //最终全部抵消后，多余的是众数。

        int remain;//最后剩下的肯定是全数组的众数
        int count=0;//记录当前假设的众数的次数 用于抵消
        int length=nums.size();
        for(int i=0;i<length;i++)
        {
            if (count==0)//更新假设对象
            {
                remain=nums[i];
                count++;
            }
            else if(nums[i]!=remain)//两两抵消
                count--;
            else//相同数，count++
                count++;
            
        }

        return remain;
    }
};