【题解】剔除相关数
【题目描述】
一个数与另一个数如果含有相同数字和个数的字符，则称两数相关。现有一堆乱七八糟的整数，里面可能充满了彼此相关的数，请你用一下手段，自动地将其剔除。
【输入描述】
每组数据前有一个N(<1000)，表示跟随的整数P(0
【输出描述】
按从小到大的顺序输出非相关数，若没有非相关数，则输出None
【样例输入】
8 213 667 3 213 43 34 677 2 3 322 232 232 0
【样例输出】
2 3 667 677 None
【题目分析】
比较简单的一道模拟题，拆分数字进行比较即可
双重for循环两两比较，把不相关的数加到新数组里
长度不相同，一定不相关。长度相同的情况下，如果有其中任何一个数字没有对应则不相关
注意特殊情况，677和667长度一样，但是6的数量和7的数量不同。（写到这里，我突然想起了桶排!）
【解题思路】
思路一：纯暴力穷举，把数一个个挨个拆开，然后做比较。
思路二：数字拆分后可以用桶排的方法来比较长度和数字是否一样。
思路三：考虑将数字转换成字符串，用字符串的特点进行比较。
【参考答案一】：纯暴力计算
#include <iostream> #include <cstring> #include <algorithm> using namespace std; int n; //数字个数 const int maxn=10001; int Length(int n){ /*每个数的长度 如100长度是3*/ int len=0; while(n){ n/=10; len++; } return len; } int Equal(int n,int m){ /* 判断每两个数的是否相等*/ int M[21],N[21]; //保存两个数分解出来的数 int t=0,k=0; while(n){ /*因为长度是相等的，所以只要一个数满足不为零就可以了*/ N[t]=n%10; M[t++]=m%10; n/=10; m/=10; } sort(N,N+t); /*进行从小到大排序*/ sort(M,M+t); for(int i=0;i<t;i++){ /*如果两个数分解出来的数不相等 说明两个数不相关*/ if(N[i]!=M[i]) return 0; } return 1; /*两个数相等，返回真*/ } int main(){ while(cin>>n&&n){ int a[maxn]; for(int i=0;i<n;i++) cin>>a[i]; sort(a,a+n); /*进行从小到大排序，主要方便输出*/ int Len[maxn],flag[maxn]; /*Len[] 保存每个数的长度，flag[]对相关数进行标记*/ memset(Len ,0 ,sizeof(Len)); /*数组清零*/ memset(flag ,0 ,sizeof(flag)); /*数组清零*/ for(int i=0;i<n;i++){ Len[i]=Length(a[i]); /*求每个数的长度*/ } for(int i=0;i<n;i++){ /*暴力解题*/ for(int j=i+1;j<n;j++){ if(Len[i]==Len[j]){ /*长度不相等就跳过了*/ if(Equal(a[i],a[j])){ /*满足相关数进行标记*/ flag[i]=1; flag[j]=1; } } } } int Ans=0; /*用来判断是不是有些数不是相关数*/ for(int i=0;i<n;i++){ if(flag[i]==0){ cout<<a[i]<<" "; Ans++; } } if(Ans==0) cout<<"None"; cout<<endl; } return 0; }【参考答案二】
(adsbygoogle = window.adsbygoogle || []).push({});