题目描述

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

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

思考题：

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

样例

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

输出：1

算法1

(快速选择) $O(n)$

因为这个数在数组中出现次数超过一半，所以排序后中位数一定是它。
所以可以用快速选择算法直接求中位数，不过会修改数组。

C++ 代码

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int n = nums.size();
        return quickselect(nums, 0, n - 1, n >> 1);
    }

    int quickselect(vector<int>& nums, int l, int r, int k)
    {
        if(l >= r) return nums[l];
        int i = l - 1, j = r + 1, tmp = nums[l + r >> 1];
        while(i < j){
            while(nums[++ i] < tmp);
            while(nums[-- j] > tmp);
            if(i < j) swap(nums[i], nums[j]);
        }
        int cnt = i - l + 1;
        if(cnt >= k) return quickselect(nums, l, j, k);
        return quickselect(nums, j + 1, r, k - cnt);
    }
};

算法2

(根据数组特性) $O(n)$

书上的解法，可以不修改数组得到答案。

C++ 代码

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