题目

• 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
• 假设数组非空，并且一定存在满足条件的数字。
• 思考题：

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

• 数据范围

数组长度 [1,1000]。

示例

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

代码

• 加减计数

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        // 遇到相同的 cnt ++    遇到不同的 cnt --
        // cnt 如果小于等于 0，再重新拿一个数，cnt 置为 1
        int cnt = 0, val = -1;
        for(auto x : nums){
            if(!cnt) val = x, cnt = 0;  // 这里置 0
            if(x == val)    cnt++;      // 这里会变为 1，一样的效果
            else    cnt--;
        }
        return val;
    }
};

代码分析：这题有技巧，如下：

遇到相同的 cnt ++ 遇到不同的 cnt --
cnt 如果小于等于 0，再重新拿一个数，cnt 置为 1

最后 val 中留下的就是出现次数超过一半的数字

题目：数组中出现次数超过一半的数字