leetCode169.多数元素+摩尔投票法

169. 多数元素 - 力扣（LeetCode）

---

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 

大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

---

---

class Solution { public: int majorityElement(vector<int>& nums) { int cand1=0,votes=0; for(const int& num:nums) { if(votes == 0) cand1 = num; // if(cand1 == num) votes++; // else votes--; votes += (cand1 == num) ? 1 : -1; } return cand1; } };

k值摩尔投票法：（推导看我的往期文章）leetCode 229. 多数元素 II + k值摩尔投票法 + 进阶 + 优化空间-CSDN博客 blog.csdn.net/weixin_41987016/article/details/134097586?spm=1001.2014.3001.5501

class Solution { public: // k值摩尔投票法 int k=2; int majorityElement(vector<int>& nums) { // 创建返回值 vector<int> res; // if (nums.empty() || nums.size() == 0) return res; if (nums.size() == 1) return nums[0]; int n = k-1, m = 2, cands[n][m]; memset(cands, 0, sizeof(cands)); for(int i=0;i<n;i++) { cands[i][0]=nums[0]; // cands[i][1]=0; } // 摩尔投票法，分为两个阶段：配对阶段 和 计数阶段 bool voteflag=0; bool matchflag = 0; for(const int &num : nums) { // 给候选人投票 for(int i=0;i<n;i++) { if(cands[i][0] == num) {cands[i][1]++;voteflag=1;break;} else voteflag=0;//投票失败 } // 有某个候选人得票 if(voteflag) continue; // 候选人配对 for(int i=0;i<n;i++) { if(cands[i][1] == 0) { cands[i][0] = num; cands[i][1]++; matchflag=1; break; } else matchflag=0; } if(matchflag) continue; for(int i=0;i<n;i++) { cands[i][1]--; } } // (2) 计数阶段 for(int i=0;i<n;i++) { if(cands[i][1]==0) cands[i][0] = INT_MAX; cands[i][1]=0; } for(const int &num : nums) { for(int i=0;i<n;i++) if (cands[i][0] == num ) { cands[i][1]++; } } for(int i=0;i<n;i++) { if (cands[i][1] > nums.size() / k ) res.push_back(cands[i][0]); } return res[0];//这里因为题目要求返回int，有需要可以返回vector } };

我的往期文章：

LCR 158. 库存管理 II 哈希 / 摩尔投票法-CSDN博客 blog.csdn.net/weixin_41987016/article/details/134094319?spm=1001.2014.3001.5501