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

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

思考题：

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

样例

1
2
3

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

输出：1

思路：

抽屉原理: 参考算法

解题代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        if(nums.size() <= 0) return 0;
        if(nums.size() == 1) return nums[0];
        int pre=nums[0] - 1,   cnt = 1;
        for(int u: nums) {
            if(pre != u) cnt--;
            else cnt++;
            if(cnt<=0) {
                cnt = 1,pre = u;
            }
        }
        
        return pre;
    }
};

找出一个数， 他的数量 是 $(n/2)+1$,