http://blog.csdn.net/wuzhekai1985/article/details/6704902
问题描述:输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个。例如输入数组{32, 321},则输出这两个能排成的最小数字32132。请给出解决问题的算法,并证明该算法。
思路:先将整数数组转为字符串数组,然后字符串数组进行排序,最后依次输出字符串数组即可。这里注意的是字符串的比较函数需要重新定义,不是比较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出现的位置,分三种情况考虑:
(1)xxxxab,用ba代替ab可以得到xxxxba,这个数字是小于xxxxab,与假设矛盾。因此排成的最小数字中,不存在上述假设的关系。
(2)abxxxx,用ba代替ab可以得到baxxxx,这个数字是小于abxxxx,与假设矛盾。因此排成的最小数字中,不存在上述假设的关系。
(3)axxxxb,这一步证明麻烦了一点。可以将中间部分看成一个整体ayb,则有ay
< ya,yb < by成立。将ay和by表示成10进制数字形式,则有下述关系式,这里a,y,b的位数分别为n,m,k。
关系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的前面。从而得出算法是正确的。
参考代码:
-
structcompare
- {
-
booloperator()(conststring&src1,conststring&src2)
- {
- strings1=src1+src2;
- strings2=src2+src1;
-
returns1<s2;
- }
- };
-
-
-
-
voidComArrayMin(int*pArray,intnum)
- {
-
inti;
-
string*pStrArray=newstring[num];
-
for(i=0;i<num;i++)
- {
- stringstreamstream;
- stream<<pArray[i];
- stream>>pStrArray[i];
- }
-
sort(pStrArray,pStrArray+num,compare());
-
for(i=0;i<num;i++)
- cout<<pStrArray[i];
- cout<<endl;
-
delete[]pStrArray;
- }
分享到:
相关推荐
剑指Offer(Python多种思路实现):把数组排成最小的数 面试45题: 题:把数组排成最小的数 题目:输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32...
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。 输出结果可能非常大,所以需要返回一个字符串而不是整数。 拼接起来的数字可能会有前导 0,最后结果不需要去掉前导...
罗穗骞《后缀数组——处理字符串的有力工具》(有算法源码和解题源码) IOI2009论文,有源码,简单易懂,方便学习后缀数组的构造和各种应用。 后缀数组是一种优秀的数据结构,在字符串匹配方面有诸多应用。
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给...
2022高考二轮复习数学 规范答题示范课——概率与统计解答题 .pdf
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE...
高考函数解题技巧课——1招破解3类函数零点高考题(手写笔记).pdf
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2...
剑指Offer(Python多种思路实现):数组中重复的数字 ...思路一:先把输入数组排序,然后从排序后的数组中从前往后找。 解题代码: def duplicate(self, numbers, duplication): if numbers==None or
第17章智慧星答题测试系统——源码
高中化学解题方法大全——燃料电池.docx
请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例1: nums1 = [1, 3] nums2 = [2] 则中位数是 2.0 示例2: nums1 = [1, 2] nums...
如果数组中存在多个幸运数,只需返回 最大 的那个。 如果数组中不含幸运数,则返回 -1 。 示例 1: 输入:arr = [2,2,3,4] 输出:2 解释:数组中唯一的幸运数是 2 ,因为数值 2 的出现频次也是 2 。 示例 2: 输入:...
初中语文阅读答题技巧秘籍——资料文档.pdf
如此一来,设置三个指针,只需要把当前合适的数放到额外空间中。 由于比较,总会有一个数组先结束,对于后结束的一个数组,如果其恰好就是最终需要返回的,则无需处理。 如果是另一个数组,则直接把它的...
博主也是第一次当博主,想要做一名...解题思路: 从左下角开始找,左下角的值m依据题目可得,m是行中最小,列中最大,故每次都将m与目标值target比较: 1.当m<target>target时,由于m为行中最小,故取值向上移动一位 3
LabVIEW 删除数组中重复元素实例 , LabVIEW8.2 编写 删除数组中重复的元素. 查找重复元素 并删除重复
罗穗骞《后缀数组——处理字符串的有力工具》(有算法源码和解题源码) IOI2009论文,有源码,简单易懂,方便学习后缀数组的构造和各种应用。 后缀数组是一种优秀的数据结构,在字符串匹配方面有诸多应用。
高考政治解题方法指导——图表型选择题PPT课件.pptx
给定一个字符串数组,数组中的元素各不相同,把一个数组里的“数组合”全部列出,比如1和2列出来为1,2,12,21.一共有4个“数组合” 输入描述: 第一行输入数为数组元素个数,第二行输入数组元素 输出...