题目

题解

详细注释见169题，这里再练习一下

1. 排序取中法

  • 时间复杂度$O(nlog{n})$，主要是排序耗费的
  • 空间复杂度$O(1)$
class Solution {//三种方法，这是1.排序后取中间数
//时间复杂度O(nlogn),主要是排序消耗时间
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()/2];
    }
};

2. 摩尔投票法

最佳方法。利用本题大于n/2的性质，

  1. 先假定当前数位众数，
  2. 若遇到这个数（包括自身）则计数值+1，遇到不同的数计数值-1。
  3. 当计数值==0的时候更改当前的假定众数，为现在遍历的数
  4. 返回最后的众数值
  • 时间复杂度$O(n)$
  • 空间复杂度$O(1)$
class Solution {
public:
    int majorityElement(vector<int>& nums) {//三种方法。2. 摩尔投票法
        int res=0;
        int count = 0;
        for(auto num:nums){
            if(count==0) res = num;
            if(res==num)count++;
            else count--;
        }
        return res;
    }
};

3. 哈希表法

记录每个数的个数，遇到大于一半地直接返回

  • 时间复杂度$O(n)$
  • 空间复杂度$O(n)$
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> m;
        for(auto num:nums){
            if(m.count(num)) m[num]++;
            else m[num]=1;
            if(m[num]>nums.size()/2) return num;
        }
        return -1;
    }
};