题目描述

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

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

思考题：

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

数据范围

数组长度 [1,1000]。

样例

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

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

摩尔投票法：

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

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

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

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

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

从前往后遍历所有数，cnt 初始为 0 ，val 初始为 -1 。

如果 cnt 为 0 ，则将 val = x ，并且 cnt = 1 。

如果 cnt 不为 0 ，则判断 val 是否等于 x ，如果等于则 cnt 加 1 ，否则减 1 。

最后得到的 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;
    }
};

欢迎大家在评论区交流~