汕尾手机网站设计,免费建立网站软件,江苏和城乡建设部网站首页,连云港网站建设开发问题描述#xff1a;输入一个正整数数组#xff0c;将它们连接起来排成一个数#xff0c;输出能排出的所有数字中最小的一个。例如输入数组{12, 567}#xff0c;则输出这两个能排成的最小数字12567。请给出解决问题的算法#xff0c;并证明该算法。 思路#xff1a;先将… 问题描述输入一个正整数数组将它们连接起来排成一个数输出能排出的所有数字中最小的一个。例如输入数组{12, 567}则输出这两个能排成的最小数字12567。请给出解决问题的算法并证明该算法。 思路先将整数数组转为字符串数组然后字符串数组进行排序最后依次输出字符串数组即可。这里注意的是字符串的比较函数需要重新定义不是比较a和b而是比较ab与 ba。如果ab ba则a b如果ab ba则a b如果ab ba则a b。比较函数的定义是本解决方案的关键。 证明为什么这样排个序就可以了呢简单证明一下。根据算法如果a b那么a排在b前面否则b排在a前面。可利用反证法假设排成的最小数字为xxxxxx并且至少存在一对字符串满足这个关系a b但是在组成的数字中a排在b前面。根据a和b出现的位置分三种情况考虑 1xxxxab用ba代替ab可以得到xxxxba这个数字是小于xxxxab与假设矛盾。因此排成的最小数字中不存在上述假设的关系。 2abxxxx用ba代替ab可以得到baxxxx这个数字是小于abxxxx与假设矛盾。因此排成的最小数字中不存在上述假设的关系。 3axxxxb这一步证明麻烦了一点。可以将中间部分看成一个整体ayb则有ay yayb by成立。将ay和by表示成10进制数字形式则有下述关系式这里ayb的位数分别为nmk。 关系1 ay ya a * 10^m y y * 10^n a a * 10^m - a y * 10^n - y a( 10^m - 1)/( 10^n - 1) y 关系2 yb by y * 10^k b b * 10^m y y * 10^k - y b * 10^m - b y b( 10^m -1)/( 10^k -1) 关系3 a( 10^m - 1)/( 10^n - 1) y b( 10^m -1)/( 10^k -1) a/( 10^n - 1) b/( 10^k -1) a*10^k - a b * 10^n - b a*10^k b b * 10^n a a b 这与假设a b矛盾。因此排成的最小数字中不存在上述假设的关系。 综上所述得出假设不成立从而得出结论对于排成的最小数字不存在满足下述关系的一对字符串a b但是在组成的数字中a出现在b的前面。从而得出算法是正确的。 参考代码
//重新定义比较函数对象
struct compare
{bool operator() (const string src1, const string src2){string s1 src1 src2;string s2 src2 src1;return s1 s2; //升序排列如果改为s1 s2则为逆序排列}
};
//函数功能 把数组排成最小的数
//函数参数 pArray为数组,num为数组元素个数
//返回值 无
void ComArrayMin(int *pArray, int num)
{int i;string *pStrArray new string[num];for(i 0; i num; i) //将数字转换为字符串{ stringstream stream;streampArray[i];streampStrArray[i];}sort(pStrArray, pStrArray num, compare()); //字符串数组排序for(i 0; i num; i) //打印字符串数组coutpStrArray[i];coutendl;delete [] pStrArray;
}
