这道题很简单,但是有好几个人问过我了,我一直答得都不好。
首先partition,期望来进行分割,但其实用bfprt的话可以常数分割。
主函数那几个分割一定要助理,麻烦的话也不麻烦,但是很容易漏下,比如while的条件,kth的判断等等
#include<iostream>
#include<vector>
#include<unordered_set>
#include<algorithm>
using namespace std;
void partition(vector<int>& a, int left, int& less, int& more, int right)
{
if(left>right)
return;
int index=right, erg = left;
more = right, less = left-1;
while(erg<more)
{
if(a[erg]<a[index])
swap(a[++less], a[erg++]);
else if(a[erg]>a[index])
swap(a[--more], a[erg]);
else
++erg;
}
swap(a[more++], a[index]);
return;
}
void dupRemove(vector<int>&a)
{
unordered_set<int>b;
for(int i=0; i<(int)a.size();)
{
if(b.end()==b.find(a[i]))
b.insert(a[i++]);
else
a.erase(a.begin()+i);
}
}
int thirdMax(vector<int>& nums) {
dupRemove(nums);
int n=(int)nums.size(), kth=n-3;
int less=-1, more=n-1;
int left=0, right=n-1;
if(n<3 && n>0)
return *max_element(nums.begin(), nums.end());
while(left<right)
{
partition(nums, left, less, more, right);
if(kth>=more)
left=more;
else if(kth<=less)
right=less;
else
return nums[less+1];
}
return nums[left];
}
int main(void)
{
vector<int>a={2,2,1};
cout<<thirdMax(a)<<endl;
return 0;
}