把数组排成最小的数

题目描述思路实现

题目描述

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

思路

这题如果用暴力思维想，数组内多个元素，排列组合的可能性很多， 可以简化成某两个相邻元素的排列组合，只有两种可能。 从头到尾两两组合并进行比较，根据比较结果实时调整位置，最终就能得到最佳的元素顺序

某两个相邻元素比较的思路：s1+s2的值若比s2+s1大，说明s2+s1才是我们想要的，对换数组中s1和s2的位置 比较具体过程： （1）元素1从数组首元素开始，元素2从元素1下一个元素开始，遍历数组 （2）把遍历到的两个相邻元素先连接成字符串（1在前和2在前两种情况）：在两个数字间加个空串，就整体变成字符串了， 再把两个字符串转换成两个整型数n1和n2，如果n2比n1小，就把元素1和元素2 在数组中的位置对换

遍历完数组后，数组中元素顺序就是最佳的了，接下来只需把所有数组元素直接连接成字符串，并返回即可

实现

public String PrintMinNumber(int [] numbers) { //比较两个字符串s1, s2大小的时候， //先将它们拼接起来，比较s1+s2和s2+s1哪个大，如果s1+s2大，那说明s2应该放前面 //遍历数组，使用两个遍历的变量i和j，一个代表s1,一个代表s2 String s=""; //存放结果 //调整数组元素的顺序，使连接后能得到最小数字 for(int i=0;i<numbers.length;i++){ for(int j=i+1;j<numbers.length;j++){ //把两个数组元素用空串连接，就变成了了一个完整的字符串，再转换成整数 int n1=Integer.valueOf(numbers[i]+""+numbers[j]); int n2=Integer.valueOf(numbers[j]+""+numbers[i]); //比较n1和n2哪个更小,默认是i+j顺序，若n2更小，就对换i和j位置 if(n2<n1){ int t=numbers[i]; numbers[i]=numbers[j]; numbers[j]=t; } } } //上述循环后，数组元素的顺序已经确定，可以得到最小数字。直接连接成字符串就行了 for(int i=0;i<numbers.length;i++){ s+=String.valueOf(numbers[i]); } return s; }

网上很多答案使用比较器来比较，但我对比较器不熟练，所以就直接调整数组元素顺序了（比较器在剑指Offer题里出场率很高啊~）