多数元素

发表于 分类于 ， 阅读次数： Waline： 本文字数： 1.5k 阅读时长 ≈ 1 分钟

169. 多数元素

给定一个大小为 n的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例：

输入：nums = [2,2,1,1,1,2,2]

输出：2

思路：

方法一：哈希表

时间，空间复杂度为：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        unordered_map<int,int> mp;
        for(int i = 0; i < n; i++){
            mp[nums[i]]++;
        }
        for(int i = 0; i < n; i++){
            if(mp[nums[i]] > (n / 2)){
                res = nums[i];
                break;
            }
        }
        return res;
    }
};

方法二：排序

时间复杂度为：O(nlogn)

1
2
3
4
5
6
7
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

方法三：摩尔投票法

这里我们重点讲摩尔投票法，时间复杂度为o(n)，空间复杂度为O(1)。

因为多数元素的次数总是大于[n/2]，那么其他元素只能小于[n/2]，所以我们选出一个候选人candidate，他本身的票数为count = 1，我们遍历数组，如果和这个数一样，那么我们票数加一，否则票数减一，如果票数为负，则我们让下一个元素当候选人，票数设为一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = nums[0];
        int count = 1;

        for(int i = 1; i < nums.size(); i++){
            if(nums[i] == candidate){
                count++;
            }else if(--count < 0){
                candidate = nums[i];
                count = 1;
            }
        }
        return candidate;
    }
};