leetCode229.多数元素II+摩尔投票法+进阶+优化空间

229. 多数元素 II - 力扣（LeetCode）

---

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。 

---

（1）哈希表

class Solution { public: // 哈希 vector<int> majorityElement(vector<int>& nums) { unordered_map<int,int> mp; for(const int& a:nums) mp[a]++; int n = nums.size() / 3; int i=0; vector<int> ans; for(auto &it:mp) { if(it.second > n) ans.push_back(it.first); } return ans; } };

(2) 摩尔投票法

class Solution { public: // 摩尔投票法 vector<int> majorityElement(vector<int>& nums) { // 创建返回值 vector<int> 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/3 count1=0; count2=0; 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 - 力扣（LeetCode） leetcode /problems/majority-element-ii/solutions/123170/liang-fu-dong-hua-yan-shi-mo-er-tou-piao-fa-zui-zh/229. 多数元素 II - 力扣（LeetCode） leetcode /problems/majority-element-ii/solutions/1060343/gong-shui-san-xie-noxiang-xin-ke-xue-xi-ws0rj/