229. Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

分析:
本题是169.Majority Element的扩展,需要两次遍历,第一次遍历选出两个候选众数,第二次求出两个众数的出现次数,最后返回出现大雨n/3的众数。

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
       int num = nums.size();
       int major0 = 0, major1 = 0, count0 = 0, count1 = 0;
       for(int i = 0; i < num; ++i)
       {
           if(major0 == nums[i])
                count0++;
           else if(major1 == nums[i])
                count1++;
           else if(count0 == 0) 
           {
               major0 = nums[i];
               count0++;
           }else if(count1 == 0) 
           {
               major1 = nums[i];
               count1++;
           }else
           {
               count0--;
               count1--;
           }
       }
        
       count0 = 0, count1 = 0; //出现次数重新置0,第二次遍历重新求出现次数
       for(int i = 0; i < num;++i)
       {
           if(nums[i] == major0) count0++;
           else if(nums[i] == major1) count1++;
       }
     
       vector<int> ret;
       if(count0 > num/3) ret.push_back(major0);
       if(count1 > num/3) ret.push_back(major1);
        
       return ret;
        
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • Question Given an integer array of size n, find all eleme...
    FlynnLWang阅读 224评论 0 0
  • Given an integer array of size n, find all elements that ...
    Jeanz阅读 168评论 0 0
  • 题目 题目很简短,给定一个包含n个数字的数组,找出所有出现次数超过 ⌊ n/3 ⌋ 次的数。要求O(n)时间复杂度...
    yxwithu阅读 221评论 0 0
  • Given an integer array of size n, find all elements that ...
    matrxyz阅读 148评论 0 0
  • 如果你对学习和总结感到怀疑了,或者有点松懈了,就看看它吧! 1、如果你今天不按时学习 交或应付总结,你将失去人生,...
    抗老达人阅读 218评论 0 0