O(n)算法

线性 $O(n)$

其实很简单,找到两个不同的数,将其删掉,得到的解与之前的相同(不妨证一下)

如果相同则跳到下一个

如果相同个数超过半数,则返回那个数

C++ 代码

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) 
    {
        if(nums.size()<=2) return nums[0] ;
        int pos=1 ;
        while(nums[pos]==nums[0]&&pos<=(nums.size()+1)/2) pos++ ;
        if(pos>(nums.size()+1)/2) return nums[0] ;
        else
        {
            nums.erase(nums.begin()+pos) ;
            nums.erase(nums.begin()) ;
            return moreThanHalfNum_Solution(nums) ;
        }
    }
};