题目描述

此题最直观的想法就是先从小到大排序完然后再第n/2的数但时间复杂度为$O(nlogn)$因此采用以下时间复杂度为$O(n)$的方法

算法1

投票法，每一个数被投票选中为1，不被选中为-1,注意只有出现的数超过一半的时候最后剩下的val才是超过一半的数

时间复杂度 $O(n)$

空间复杂度 $O(1)$

C++ 代码

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int cnt=1;
        int val=nums[0];
        for(int i=1;i<nums.size();i++)
        {
            if(val==nums[i])
                cnt++;
            else
                cnt--;
            if(cnt==0)//cnt0=0代表到位置i为止，等于val的数和不等于val的数的个数相同
            {
                cnt=1;
                val=nums[i];
            }
        }
        return val;//最后留下的val一定是出现次数超过一半的数
    }
};

算法2

哈希表

时间复杂度 $O(n)$

空间复杂度 $O(n)$

C++ 代码

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int cnt=1;
        map<int,int> a;
        for(auto num:nums)
        {
            a[num]++;
            if(a[num]>nums.size()/2)
                return num;
        }
        return 0;
    }
};

算法3

快排

时间复杂度 $O(n)$

空间复杂度 $O(logn)$

C++ 代码

class Solution {
public:
    int quick_sort(vector<int>& nums,int l,int r,int n)
    {
        if(l>=r) return nums[l];
        int x=nums[(l+r)>>1],i=l-1,j=r+1;
        while(i<j)
        {
            while(nums[++i]<x);
            while(nums[--j]>x);
            if(i<j) swap(nums[i],nums[j]);
        }
        int sl=j-l+1;
        if(n>sl) return quick_sort(nums,j+1,r,n-sl);
        return quick_sort(nums,l,j,n);
    }
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int cnt=1;
        return quick_sort(nums,0,nums.size()-1,nums.size()/2);//nums.size()/2+1也可以
    }
};