题解 | #排列#

思路：1.一个数最多出现两次，超过两次，输出-1，记录这个数两次出现的数组下标位置。2.统计1~n中没有出现的数字。3.两两组合构成排列。
代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	vector<int>a(n);
	pair<int,int>hash[100010];
	for(int i=1;i<=n;i++)
	{
		hash[i].first=-1;
		hash[i].second=-1;
	}
	map<int,int>mp;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		mp[a[i]]++;	
	} 
	for(int i=0;i<n;i++)
	{
		if(hash[a[i]].first==-1)
		hash[a[i]].first=i;
		else if(hash[a[i]].second==-1)
		hash[a[i]].second=i;
		else
		{
			cout<<-1<<endl;
			return 0;
		}
	}
	vector<int>zero;
	for(int i=1;i<=n;i++)
	{
		if(mp[i]==0)
		zero.push_back(i);
	}
	
//	for(int i=1;i<=n;i++)
//	cout<<hash[i].first<<" "<<hash[i].second<<endl;
//	for(auto i:zero)
//	cout<<i<<" ";
//	cout<<endl;
	int cnt=0;
	vector<int>b1(n,0);
	vector<int>b2(n,0);
	for(int i=0;i<n;i++)
	{
		if(hash[a[i]].first!=-1&&hash[a[i]].second==-1)
		{
			b1[i]=a[i];
			b2[i]=a[i];
		}
		if(hash[a[i]].first!=-1&&hash[a[i]].second!=-1&&b1[i]==0&&b1[hash[a[i]].second]==0&&b2[i]==0&&b2[hash[a[i]].second]==0)
		{
			b1[i]=a[i];
			b1[hash[a[i]].second]=zero[cnt];
			b2[i]=zero[cnt];
			b2[hash[a[i]].second]=a[i];
			cnt++;
		}
	}
	for(auto i:b1)
	cout<<i<<" ";
	cout<<endl;
	for(auto i:b2)
	cout<<i<<" ";
	cout<<endl;
	return 0;
}