开发网站网络公司排行,彩票网站建设开发,腾讯营销,晋州做网站的联系电话229. 多数元素 II - 力扣#xff08;LeetCode#xff09; 给定一个大小为 n 的整数数组#xff0c;找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。 进阶#xff1a;尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。 #xff08;1#xff09;哈希表
class …229. 多数元素 II - 力扣LeetCode 给定一个大小为 n 的整数数组找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。 进阶尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。 1哈希表
class Solution {
public:// 哈希vectorint majorityElement(vectorint nums) {unordered_mapint,int mp;for(const int a:nums) mp[a];int n nums.size() / 3;int i0;vectorint ans;for(auto it:mp) {if(it.second n) ans.push_back(it.first); }return ans;}
};
(2) 摩尔投票法
class Solution {
public:// 摩尔投票法vectorint majorityElement(vectorint nums) {// 创建返回值vectorint res;if (nums.empty() || nums.size() 0) return res;// 初始化两个候选人candidate和他们的计票int cand1 nums[0],count1 0;int cand2 nums[0],count2 0;// 摩尔投票法分为两个阶段配对阶段 和 计数阶段// (1) 配对阶段for(const int num : nums) {// 投票if(cand1 num) {count1;continue;}if(cand2 num) {count2;continue;}// 第 1 个候选人配对if(count1 0) {cand1 num;count1;continue;}// 第 2 个候选人配对if(count2 0) {cand2 num;count2;continue;}count1--;count2--;}// (2)计数阶段 : 找到了两个候选人之后需要确定票数是否满足大于 N/3count10;count20;for(const int num : nums) {if (cand1 num) count1;else if (cand2 num) count2;}if (count1 nums.size() / 3) res.push_back(cand1);if (count2 nums.size() / 3) res.push_back(cand2);return res;}
};
推荐和参考文章
229. 多数元素 II - 力扣LeetCodehttps://leetcode.cn/problems/majority-element-ii/solutions/123170/liang-fu-dong-hua-yan-shi-mo-er-tou-piao-fa-zui-zh/229. 多数元素 II - 力扣LeetCodehttps://leetcode.cn/problems/majority-element-ii/solutions/1060343/gong-shui-san-xie-noxiang-xin-ke-xue-xi-ws0rj/
