本文共 991 字，大约阅读时间需要 3 分钟。

解法1：哈希表

思想：

​ 用哈希表记录出现的个数，有超过一半的就返回

复杂度：

​ 时间：O(n)

​ 空间：O(n)

代码：

class Solution {   public:    int majorityElement(vector
   
    & nums) {           unordered_map
    
     nums_map;        for(int i : nums){               ++nums_map[i];            if(2 * nums_map[i] > nums.size())                return i;        }        return -1;    }};
    
   

解法2：排序取中间数

思想：

​ 数字出现次数多于一半，那么排序后必定在中间

复杂度：

​ 时间：O(nlogn)

​ 空间：O(1)

代码：

class Solution {   public:    int majorityElement(vector
   
    & nums) {           sort(nums.begin(), nums.end());        return nums[nums.size() / 2];    }};
   

解法3：摩尔投票法

思想：

​ 可以理解成混战极限一换一，不同的两者一旦遇见就同归于尽，最后活下来的值都是相同的，即要求的结果

复杂度：

​ 时间：O(n)

​ 空间：O(1)

代码：

class Solution {   public:    int majorityElement(vector
   
    & nums) {           int count = 0, res = 0;        for(int i : nums){               //如果count为0，遇到的下一个数设为res            if(count == 0)                res = i;            //遇到不同的数减一(一换一)，遇到相同的数加一            count +=  res == i ? 1 : -1;        }        return res;    }};
   

转载地址：http://iidq.baihongyu.com/