题目描述

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

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

思考题：

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

样例

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

输出：1

算法

(别的题解) $O(n)$

Talk is cheap

时间复杂度 $O(n)$

空间复杂度 $O(1)$

参考文献 无

C++ 代码

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

C 代码

int moreThanHalfNum_Solution(int* nums, int numsSize) {
    int candi=nums[0],cnt=1;
    for(int i=0;i<numsSize;i++){
        int v=nums[i];
        if(v==candi)cnt++;
        else{
            cnt--;
            if(cnt==0){
                candi=v;
                cnt=1;
            }
        }
    }
    return candi;
}

Java 代码

class Solution {
    public int moreThanHalfNum_Solution(int[] nums) {
        int candi=nums[0];
        int cnt=1;
        for(int i=0;i<nums.length;i++){
            int v=nums[i];
            if(v==candi)cnt++;
            else{
                cnt--;
                if(cnt==0){
                    candi=v;
                    cnt=1;
                }
            }
        }
        return candi;
    }
}

Python 代码

class Solution(object):
    def moreThanHalfNum_Solution(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        candi,cnt=nums[0],1
        for v in nums:
            if v==candi:
                cnt+=1
            else:
                cnt-=1
                if cnt==0:
                    candi=v
                    cnt=1
        return candi

Javascript 代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var moreThanHalfNum_Solution = function(nums) {
    var candi=nums[0],cnt=1;
    for(var i=0;i<nums.length;i++){
        var v=nums[i];
        if(v==candi)cnt++;
        else{
            cnt--;
            if(cnt==0){
                candi=v;
                cnt=1;
            }
        }
    }
    return candi;
};

Python3 代码

class Solution(object):
    def moreThanHalfNum_Solution(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        candi,cnt=nums[0],1
        for v in nums:
            if v==candi:
                cnt+=1
            else:
                cnt-=1
                if cnt==0:
                    candi=v
                    cnt=1
        return candi

Go 代码

func moreThanHalfNum_Solution(nums []int) int {
    candi,cnt:=nums[0],1
    for _,v:=range nums{
        if v==candi{
            cnt++
        }else{
            cnt--
            if cnt==0{
                candi=v
                cnt=1
            }
        }
    }
    return candi
}