剑指offer第二版——面试题45（java）

面试题：吧数组排成最小的数

题目：

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接处的搜优数字中最小的一个

如{3,32,321}，则打印出321323

方法：

找到一个排序规则，数组根据这个规则排序之后能排成一个最小的数字

排序规则，就是用于比较两个数，按前后组合之后，哪个数更小。如数a和b，若ab<ba，则应把a放在前面，所以a更小（a和b不一定是一个1位数，可能是>10的数）

有了排序规则后，根据排序规则对数组进行排序，最后将排序结果依次拼接，即为要求的数字

注意：要意识到将两个int型的整数拼接起来得到的数字可能会超出int型数字能表达的范围，导致数字溢出，所以可用字符串表示数字，能简便地解决问题

 

代码：

public class Q45 { public static void main(String[] args) { int[] a = new int[] {3,32,321}; minComb(a); showList(a); } public static void minComb(int[] a) { if(a.length==0) { return ; } if(a.length==1) { return ; } System.out.println("----- change location -----"); for(int i=0;i<a.length;i++) { for(int j=i+1;j<a.length;j++) { System.out.printf("%d \t%d",a[i],a[j]); if(compare(a[i], a[j])==1) { int temp = a[i]; a[i] = a[j]; a[j] = temp; System.out.printf("\t:change"); } System.out.println(); } } System.out.println("----------- end -----------"); } // a应该放在前面返回0 b应放在前面返回1 public static int compare(int a,int b) { String astr = a+""; String bstr = b+ ""; String abstr = astr+bstr; String bastr = bstr+astr; for(int i=0;i<abstr.length();i++) { if(abstr.charAt(i)>bastr.charAt(i)) { return 1; } if(abstr.charAt(i)<bastr.charAt(i)) { return 0; } } return 0; } public static void showList(int[] a) { System.out.print("\nmin number:"); for(int i=0;i<a.length;i++) { System.out.print(a[i]); } } }