输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。

╰+哭是因爲堅強的太久メ 2022-04-05 10:44 159阅读 0赞

## 题目： 输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。 ##

例如输入数组\{122,12,123\}，则输出这两个能排成的最小数字12122123。

思路：  
新排序规则：从整数数组中取出两个数a和b,将a和b转化成字符串"a"和"b",再分别把"a"和"b"拼接成"ab"和"ba"，  
再把"ab"和"ba"转出数字ab和ba，通过比较ab和ba的大小关系得出“谁排在前，谁排在后”。  
1）如果ab < ba，  
则a << b，数字a排在数字b的前面；（注意这里的a<<b不代表他们的大小关系，而是代表位置顺序的前后关系）  
2）如果ab > ba，  
则a >> b，与上面相反；  
3）如果ab = ba，  
则a = b，说明a和b为相同数字，谁前谁后都可以（我们按a在前b在后排）。  
我们规定通过以上方式排序，能排出的数字最小。

例：如果a和b分别为12和122，那么ab和ba则分别为12122和12212；  
因为12122<12212,  
那么，12<<122,所以12排在122的前面。

证明（反证法）：  
假设:如果存在ab>ba,那么a排在b前面得到的数最小;(接下来我们要做的是通过“a排在b前面”，看能不能推出“ab>ba”)  
（1） 假设xxxxab是数组中能排出的所有数字中最小的，用ba代替ab得到xxxxba，  
因为xxxxab<xxxxba则有：ab<ba，结论与假设矛盾，故不成立

（2） 假设abxxxx是数组中能排出的所有数字中最小的，用ba代替ab得到baxxxx，  
因为abxxxx<baxxxx,则有：ab<ba,结论与假设矛盾，故不成立

（3） 假设axxxxb是数组中能排出的所有数字中最小的,  
我们把axxxxb,整体看作ayb,y代表“xxxx”;  
根据我们假设的规则等到ay<ya,yb<by;  
假设a，y，b的位数分别为n，m，k(n,m,k>=1)  
字符串-----对应的十进制值  
ay=a \* 10^m + y  
ya=y \* 10^n + a  
yb=y \* 10^k + b  
by=b \* 10^m + y

关系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  
=> ab< ba  
与原假设ab>ba矛盾，故原假设不成立

综上所述:得出假设不成立，从而得出结论：对于排成的最小数字，不存在满足下述关系：  
如果存在ab>ba,那么a排在b前面得到的数最小。

从而得出正确的结论：如果存在ab<ba,那么a排在b前面得到的数最小。  
**代码**  
import java.util.Scanner;

public class Demo02 \{  
public static void main(String\[\] args)\{  
Scanner sc=new Scanner([System.in][]);  
System.out.println(“请输入数组元素个数：”);  
int n=sc.nextInt();  
int\[\] arr=new int\[n\];  
System.out.println(“请输入数组元素：”);  
for (int i = 0; i < arr.length; i++)\{  
arr\[i\]=sc.nextInt();  
\}  
System.out.print("\{");  
for (int i = 0; i < arr.length; i++)\{  
if(i==arr.length-1)  
System.out.print(arr\[i\]+"\}");  
else  
System.out.print(arr\[i\]+",");  
\}  
System.out.println();  
QuickSort(arr,0,arr.length-1);  
String str="";  
for (int i = 0; i < arr.length; i++)\{  
str=str+arr\[i\];  
\}  
System.out.println(“最小数为:”+str);  
\}  
//快速排序  
public static void QuickSort(int arr\[\],int \_left,int \_right)\{  
int right=\_right;  
int left=\_left;  
int temp=0;  
if(left<=right)\{  
temp=arr\[left\];  
while(left!=right)\{  
while(right>left&&Compare(arr\[right\],temp))  
right–;  
arr\[left\]=arr\[right\];  
while(left<right&&Compare(temp,arr\[left\]))  
left++;  
arr\[right\]=arr\[left\];  
\}  
arr\[right\]=temp;  
QuickSort(arr,\_left,left-1);  
QuickSort(arr,right+1,\_right);  
\}  
\}  
//按新的排序规则重写比较方法  
public static boolean Compare(int a,int b)\{  
String s1=""+a;  
String s2=""+b;  
String s3=s1+s2;  
int k1=Integer.parseInt(s3);  
String s4=s2+s1;  
int k2=Integer.parseInt(s4);  
if(k1>=k2)  
return true;  
else  
return false;  
\}

}

[System.in]: http://System.in