力扣-229题求众数 II（C++）- 摩尔投票法+有价值

系统管理员 2022-09-16 15:28 173阅读 0赞

题目链接：[https://leetcode-cn.com/problems/majority-element-ii/][https_leetcode-cn.com_problems_majority-element-ii]  
题目如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]  
思路：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

class Solution {
        
    public:
        vector<int> majorityElement(vector<int>& nums) {
        
            vector<int> result;
            int candidate1=-1,candidate2=-1;
            int count1=0,count2=0;
    
            for(auto num:nums){
        
                if(count1>0&&num==candidate1) count1++;//如果该元素为第一个元素，则+1
                else if(count2>0&&num==candidate2) count2++;//如果该元素是第二个元素，则+1
                else if(count1==0) {
        candidate1=num;count1++;}//第一个元素需要换人
                else if(count2==0) {
        candidate2=num;count2++;}//第二个元素需要换人
                else {
        count1--;count2--;}//如果三个元素均不相同，则互相抵消1次
            }
    		
    		//记录两个有票的候选人分别有多少人投它
            int cnt1=0,cnt2=0;
            for(auto num:nums){
        
                if(count1>0&&num==candidate1) cnt1++;
                if(count2>0&&num==candidate2) cnt2++;
            }
    
            //判断出现的次数是否满足题意要求
            if(count1>0&&cnt1>nums.size()/3) result.push_back(candidate1);
            if(count2>0&&cnt2>nums.size()/3) result.push_back(candidate2);
    
            return result;
        }
    };

[https_leetcode-cn.com_problems_majority-element-ii]: https://leetcode-cn.com/problems/majority-element-ii/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/2a62dd14edf84bc98d1a721e33918da4.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/6b28f08257eb4e78ae9678606365a17f.png