题目描述

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

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

思考题：

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

样例

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

输出：1

C++ 代码

    int moreThanHalf(vector<int> &nums) {
        int cnt = 1;
        int tar = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] == tar) cnt++;
            else cnt--; 
            if (cnt++ == 0) tar = nums[i];
        }
        cnt = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == tar) cnt++;
        }
        if (cnt > nums.size()/2) return tar;
    }

follow up: 如果是出现次数刚好一半呢？

C++ 代码

    int HalfNum_Solution(vector<int>& nums) {
        // 沿用超过一半的逻辑
        int tar = moreThanHalf(nums);
        int cnt = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == tar) cnt++;
        }
        if (cnt == nums.size()/2) return tar;
        else {
            // 丢掉最后一个数（即刚刚求出的tar）
            vector<int> v = nums;
            v.pop_back();
            return moreThanHalf(v);
        }
    }