leetcode(18)

leetcode(18)

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.

 


class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> res;

//定义两个候选变量,以及他们的计数

int candidate1=0;
int candidate2=1;
int count1=0;
int count2=0;
for(int i=0;i<nums.size();i++)
{

if(candidate1==nums[i])
count1++;
else if(candidate2==nums[i])
count2++;
else if(count1==0)
{
candidate1=nums[i];
count1++;
}
else if(count2==0)
{
candidate2=nums[i];
count2++;
}
else {
count2--;
count1--;
}
}
if(count(nums.begin(),nums.end(),candidate1)>nums.size()/3)
res.push_back(candidate1);
if(candidate1!=candidate2&&count(nums.begin(),nums.end(),candidate2)>nums.size()/3)
res.push_back(candidate2);
return res;
}
};




So BadJust So SoGoodCoolPretty Cool (还没人评过分呢!)
Loading...

发表评论

电子邮件地址不会被公开。 必填项已用*标注