剑指offer 40. 数组中出现次数超过一半的数字

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：剑指offer系列题解
📝原题地址：题目地址
📣专栏定位：为找工作的小伙伴整理常考算法题解，祝大家都能成功上岸！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

题目描述

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

假设数组非空，并且一定存在满足条件的数字。

思考题：

• 假设要求只能使用 O(n) 的时间和额外 O(1) 的空间，该怎么做呢？

数据范围

数组长度 [1,1000]。

样例

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

输出：1
1
2
3

方法一：摩尔投票法 O(n)

摩尔投票法：

设输入数组 nums 的众数即出现的次数超过一般的数字为 x ，数组长度为 n 。

则一定满足如下两个条件：

1. 假设记众数的票数为 +1 ，非众数的票数为 -1 ，则所有的票数之和一定大于 0 。

2. 若数组的前 a 个数字的票数和等于 0 ，则数组剩余的 (n−a) 个数字的票数和一定大于 0 ，即后 (n-a) 个数字的众数仍为 x 。

所以这道题方法比较奇妙，我们要用一个数 cnt 来记录当前票数，用 val 来记录当前值，步骤如下：

1. 从前往后遍历所有数，cnt 初始为 0 ，val 初始为 -1 。
   1. 如果 cnt 为 0 ，则将 val = x ，并且 cnt = 1 。
   2. 如果 cnt 不为 0 ，则判断 val 是否等于 x ，如果等于则 cnt 加 1 ，否则减 1 。
2. 最后得到的 val 一定是最终答案。

我们拿题目的例子来举例，看看具体是如何实现的：

第一步： x = 1 ，且 cnt = 0 ，故令 val = x = 1 且 cnt = 1 。

第二步： x = 2 ，且 cnt != 0 && x != val ，故令 cnt-- 。

第三步： x = 1 ，且 cnt = 0 ，故令 val = x = 1 且 cnt = 1 。

第四步： x = 1 ，且 cnt != 0 && x == val ，故令 cnt++ 。

第五步： x = 3 ，且 cnt != 0 && x != val ，故令 cnt-- 。

第六步： 返回 val = 1 即该数组出现次数超过一半的数字。

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int val = -1, cnt = 0;
        for (auto x : nums)
        {
            if (!cnt)    val = x, cnt = 1;
            else
            {
                if (val == x)  cnt++;
                else    cnt--;
            }
        }
        return val;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

欢迎大家在评论区交流~