欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode算法题169:多数元素

程序员文章站 2022-03-15 20:33:08
...

题目:

LeetCdoe题目地址

方法1:排序

思路:由于多数元素的占比超过数组的一半,所以通过排序后,位于数组正中间的元素必定是众数.
代码:

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

方法2:哈希表

思路:通过建立数值-出现次数的pair,统计数组中出现次数最多的元素
代码:

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counts;
        int majority = 0, cnt = 0;
        for (int num: nums) {
            ++counts[num];
            if (counts[num] > cnt) {
                majority = num;
                cnt = counts[num];
            }
        }
        return majority;
    }
};

方法3:Boyer-Moore 投票算法(转自LeetCode答案)

思路:如果我们把众数记为 +1,把其他数记为 -1,将它们全部加起来,显然和大于 0,从结果本身我们可以看出众数比其他数多。
代码:

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = -1;
        int count = 0;
        for (int num : nums) {
            if (num == candidate)
                ++count;
            else if (--count < 0) {
                candidate = num;
                count = 1;
            }
        }
        return candidate;
    }
};

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
相关标签: leetcode