# 229.Majority Element II

## August 16, 2016

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.

Hint:

How many majority elements could it possibly have?

class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int curIndex1=0,curIndex2=0,count1=0,count2=0;
int size=nums.size(),i=0,tri=size/3;
vector<int>res;
for(i=0;i<nums.size();i++){
if(nums[i]==nums[curIndex1])
count1++;
else if(nums[i]==nums[curIndex2])
count2++;
else if(!count1){
count1=1;
curIndex1=i;
}
else if(!count2){
count2=1;
curIndex2=i;
}
else{
count1--;
count2--;
}
}
count1=0;
count2=0;
for(i=0;i<nums.size();i++){
if(nums[i]==nums[curIndex1])
count1++;
else if(nums[i]==nums[curIndex2])
count2++;
}
if(count1>tri)
res.push_back(nums[curIndex1]);
if(count2>tri)
res.push_back(nums[curIndex2]);
return res;
}
};


### 学籍管理系统文档

#### 北邮教务系统评教脚本

Published on September 17, 2017

#### 72.Edit distance

Published on September 17, 2017