LeetCode算法题169:多数元素
程序员文章站
2022-03-15 20:33:08
...
题目:
方法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刷题:多数元素
推荐阅读
-
【leetcode 简单】第十八题 删除排序链表中的重复元素
-
python(leetcode)-重复元素算法题
-
【每日一道算法题】Leetcode之longest-increasing-path-in-a-matrix矩阵中的最长递增路径问题 Java dfs+记忆化
-
#leetcode刷题之路27-移除元素
-
【重拾算法~Leetcode每日一题】309.最佳买卖股票时机含冷冻期(难度:中等)
-
LeetCode刷题|算法归类|贪心算法介绍及各算法题合辑(持续补充)
-
LeetCode算法题(数组相关)(二)——两数之和
-
leetcode 算法题1046 (简单277) 最后一块石头的重量
-
力扣网 | 算法面试题汇总 | 开始之前 | LC 多数元素
-
数据结构线段树介绍与笔试算法题-LeetCode 307. Range Sum Query - Mutable--Java解法