海珠建网站的公司,化妆品软文推广范文,福建建设执业资格注册中心网站,咨询公司属于什么行业169. 多数元素 - 力扣#xff08;LeetCode#xff09; 给定一个大小为 n 的数组 nums #xff0c;返回其中的多数元素。多数元素是指在数组中出现次数
大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的#xff0c;并且给定的数组总是存在多数元素。 class Solution {
publ…169. 多数元素 - 力扣LeetCode 给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数
大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的并且给定的数组总是存在多数元素。 class Solution {
public:int majorityElement(vectorint nums) {int cand10,votes0;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博客https://blog.csdn.net/weixin_41987016/article/details/134097586?spm1001.2014.3001.5501
class Solution {
public:// k值摩尔投票法int k2;int majorityElement(vectorint nums) {// 创建返回值vectorint 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 i0;in;i) {cands[i][0]nums[0];// cands[i][1]0;}// 摩尔投票法分为两个阶段配对阶段 和 计数阶段bool voteflag0;bool matchflag 0;for(const int num : nums) {// 给候选人投票for(int i0;in;i) {if(cands[i][0] num) {cands[i][1];voteflag1;break;}else voteflag0;//投票失败}// 有某个候选人得票if(voteflag) continue;// 候选人配对for(int i0;in;i) {if(cands[i][1] 0) {cands[i][0] num;cands[i][1];matchflag1;break;}else matchflag0;}if(matchflag) continue;for(int i0;in;i) {cands[i][1]--;}}// (2) 计数阶段for(int i0;in;i) {if(cands[i][1]0) cands[i][0] INT_MAX;cands[i][1]0;}for(const int num : nums) {for(int i0;in;i) if (cands[i][0] num ) {cands[i][1];}}for(int i0;in;i) {if (cands[i][1] nums.size() / k ) res.push_back(cands[i][0]);}return res[0];//这里因为题目要求返回int有需要可以返回vector}
};
我的往期文章
LCR 158. 库存管理 II 哈希 / 摩尔投票法-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/134094319?spm1001.2014.3001.5501
