题目描述

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

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

样例

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

输出：1

算法

(模拟)

1. 新建2个变量val和cnt。val存储的是当前数组中出现次数较多的那个，cnt则是val的 相对 出现次数，相对其他数的出现次数。
2. 如果cnt为0，分2种情况，一种是还没遍历过数。另一种是前面的数中，有2个数出现了相同的次数。
3. 当cnt为0的时候，我们将val置为新的x。同时记录cnt++为val这个数字出现的次数
4. 如果遍历到下一个数，与当前val存储的数不一样，就抵消掉，cnt –。 val不用动，因为当cnt为0的时候，也就是val当前存的数字被抵消完的时候，后面的数会直接覆盖当前的val。
5. 因为最终的答案ans出现了超过一半，所以除了这个数以外，其他数再抵消，最后ans还是会剩下，所以最后的答案就是val中存储的值。

时间复杂度

$O(n)$的时间复杂度：把数组遍历了一遍，所以是$O(n)$
$O(1)$的空间复杂度：新开了3个int型变量，cnt val x，$O(3)$也就是$O(1)$

C++ 代码

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int val, cnt;
        for(auto x : nums)
        {
            if(cnt == 0) val = x, cnt ++;
            else
            {
                if(x == val) cnt ++;
                else cnt --;
            }
        }

        return val;
    }
};

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla