玩命加载中 . . .

169-多数元素

LeetCode

发布日期: 2021-06-27

LeetCode 169. Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than $\lfloor n / 2 \rfloor$ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

method 1: 哈希表

hash记录每个数字出现的次数

int majorityElement(vector<int>& nums) {
    int n = nums.size();
    n /= 2;
    unordered_map<int, int> hash;
    for (int i = 0; i < nums.size(); ++i) {
        hash[nums[i]]++;
        if (hash[nums[i]] > n) return nums[i];
    }
    return 0;
}

时间复杂度：$O(n)$
空间复杂度：$O(n)$

method 2: 双指针

先排序，把相同元素放在一起，再用双指针找相同元素出现次数
[l,r)区间内都是相同的元素

int majorityElement(vector<int>& nums) {
    int size = nums.size();
    size /= 2;
    sort(nums.begin(), nums.end());
    int l = 0, r = 0;
    while (r < nums.size()) {
        int cnt = 0;
        while (r < nums.size() && nums[r] == nums[l]) r++;
        cnt = r - l;    // [l,r)区间的元素个数
        if (cnt > size) return nums[l];
        else l = r;
    }
    return 0;
}

时间复杂度：$O(nlogn+n)$
空间复杂度：如果使用语言自带的排序算法，需要使用$O(logn)$的栈空间

由于众数出现的频率大于n/2，所以在排序之后众数必存在于下标[n/2]处，直接返回

int majorityElement(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    return nums[nums.size() / 2];
}

时间复杂度：$O(nlogn)$
空间复杂度：$O(nlogn)$

method 3: 摩尔投票法

众数：出现次数大于n/2的数
遇到相同的数，就投一票，遇到不同的数，就减一票，最后还存在票的数就是众数

int majorityElement(vector<int>& nums) {
    int ret = -1;
    int count = 0;
    for (auto num : nums) {
        if (count == 0) ret = num;  // count=0就重新取值
        if (num == ret) count++;    // 相同就加票
        else count--;               // 不同就减票
    }
    
    return ret;
}