剔除相关数 （C++代码）

解题思路:    

    使用STL中的set集合。可以自动排序，并保证不重复插入。

    （1）先定义一个转换函数change()实现：把原来输入的整数x里面的数字的重新从小到大排列组合成新的整数，并返回重新排列之后的整数。

    （2）这一题用了两个集合s1,s2；

    （3）s1保存的是插入的原整数x转换后的整数y。

    （4）s2保存的是插入的整数x，并保证剔除相关数。

    （5）通过判断把转换数y是否成功插入到集合s1来决定,是否把原数x插入到集合s2中；

    （6）如果y成功插入到s1中，说明没有相关数，则把原数x插入到s2中；否则插入不成功，同时要从集合s2中剔除相关数。

参考代码:

//难点在于如何判断把x插入到集合s1中是否成功，如果不成功，则说明插入的x是某一个数的相关数，此时要把
//集合s2中的相关数剔除。我是判断插入前后的长度是否增加来判断插入是否成功的。
#include<bits/stdc++.h> 
using namespace std; 
int change(int x)  //转换函数，把整数x里面数字的重新从小到到排列，赋值给y，返回重新排列之后的整数
{
	int y;
	char temp[20];
	sprintf(temp,"%d",x);
	sort(temp,temp+strlen(temp));
	sscanf(temp,"%d",&y);
	return y;	
} 
int main() 
{	
	int n;
	while(cin>>n && n)
	{		
		int x,y;
		set<int> s1,s2;
		for(int i=0;i<n;i++)
		{
			cin>>x;
			y=change(x);
			int len=s1.size();
			s1.insert(y);
			if(s1.size()>len) //插入成功，长度增加1，所以长度大于插入之前的长度 
				s2.insert(x);
			else  //插入不成功，说明有重复的 
			{
				set<int>::iterator it;		
				for(it=s2.begin();it!=s2.end();it++) //遍历集合s2，把重复的删除	
				{
					int num=change(*it);
					if(y==num)
					{
						s2.erase(it);
						break;
					} 	
				}						
			}				
		}
		if(s2.size()==0)
		{
			cout<<"None"<<endl;			
		}
		else
		{
			set<int>::iterator it1;		
			for(it1=s2.begin();it1!=s2.end();it1++)
				cout<<*it1<<" ";
			cout<<endl;				
		}
	} 	
	return 0;
}

//难点在于如何判断把x插入到集合s1中是否成功，如果不成功，则说明插入的x是某一个数的相关数，此时要把
//集合s2中的相关数剔除。通过查询发现可以用另外的方式判断插入是否成功。
#include<bits/stdc++.h> 
using namespace std; 
int change(int x)  //转换函数，把整数x里面数字的重新从小到到排列，赋值给y，返回重新排列之后的整数
{
	int y;
	char temp[20];
	sprintf(temp,"%d",x);
	sort(temp,temp+strlen(temp));
	sscanf(temp,"%d",&y);
	return y;	
} 
int main() 
{	
	int n;
	while(cin>>n && n)
	{		
		int x,y;
		set<int> s1,s2;
		for(int i=0;i<n;i++)
		{
			cin>>x;
			y=change(x);
			pair<set<int>::iterator, bool> pair1;        
        	pair1 = s1.insert(y); 
			if(pair1.second)  //插入成功，pair1.second的值为true
				 s2.insert(x);      
        	else   //插入不成功，说明有重复的 
			{
				set<int>::iterator it;		
				for(it=s2.begin();it!=s2.end();it++) //遍历集合s2，把重复的删除	
				{
					int num=change(*it);
					if(y==num)
					{
						s2.erase(it);
						break;
					} 	
				}						
			}				
		}
		if(s2.size()==0)
		{
			cout<<"None"<<endl;			
		}
		else
		{
			set<int>::iterator it1;		
			for(it1=s2.begin();it1!=s2.end();it1++)
				cout<<*it1<<" ";
			cout<<endl;				
		}
	} 	
	return 0;
}