414. 第三大的数

这道题很简单,但是有好几个人问过我了,我一直答得都不好。
首先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;
}
上一篇:414. 第三大的数


下一篇:【基于微信小程序的社区电商平台】需求分析心得——小豆芽