四川省建设监理协会网站,如何建立一个自己的网址,fusion做电影网站卡死,wordpress 采集文章 图片不显示输入一个正整数数组#xff0c;把数组里所有数字拼接起来排成一个数#xff0c;打印能拼接出的所有数字中最小的一个。 例如输入数组 [3,32,321][3,32,321]#xff0c;则打印出这 33 个数字能排成的最小数字 321323321323。 数据范围 数组长度 [0,500][0,500]。 样例#x… 输入一个正整数数组把数组里所有数字拼接起来排成一个数打印能拼接出的所有数字中最小的一个。 例如输入数组 [3,32,321][3,32,321]则打印出这 33 个数字能排成的最小数字 321323321323。 数据范围 数组长度 [0,500][0,500]。 样例 输入[3, 32, 321] 输出321323 注意输出数字的格式为字符串。 解题思路 首先假设数组内的数为 [a, b, c]。若定义一个新的排序方法即 ab ba,即a在头部的拼接结果比b在头部的拼接结果大那么就交换a,b在数组内的位置。以这种判断方式排列出来的新数组从前往后拼接起来就是我们本题需要的最小数。 以下是证明上述排序方式是有意义的
设a, b, c 的位数分别为n , m , k。
1.若 ab ba 且 ab ba是否能证明 ab ba。
证明由于ab与ba位数相同在数值上比较本假设理应成立所以此排序满足反对称性。
2.若 ab ba 且 bc cb,是否能证明 ac ca。
证明ab a*10^m b, ba b*10^n aac a*10^k c, ca c*10^n a; 由 ab ba 得 a/b (10^n - 1 )/(10^m - 1)
由 bc cb 得b/c (10^m - 1)/(10^k - 1)
只需证明 a/c (10^n - 1)/(10^k - 1)
结论显然成立。即此排序方法满足传递性。
由于sort()方法核心是快速排序快排核心就是反对称性特定情况唯一与 传递性让数据有梯度。所以此新定义得排序方法有意义。 最后我们只需证明我们排序后的数组就是最优数组即可
设我们排序后的数组是 [a, b, c, d]那么最小数就是 abcd
利用反证法
假设最小数是acbd,由于a,d所处位置一样所以比较bc,cb大小即可
由我们的新排序定义可知 bc cb 所以 abcd acbd,所以假设不成立。
即排序后的数组就是最优数组。
理论成立代码如下
class Solution {public String printMinNumber(int[] nums) {Integer a[] new Integer[nums.length];for(int i 0; i nums.length; i ) a[i] nums[i];//只能转换成Integer类Arrays.sort(a, new ComparatorInteger() {public int compare(Integer o1, Integer o2) {//新排序方法String a o1;String b o2;if(Integer.valueOf(a b) Integer.valueOf(b a))return 1;//交换位置else return -1;//不换}});String s1 ;for(int i 0; i a.length; i ) s1 s1 a[i];return s1;}
}
