将数组重新排序以构造最小值
题目描述
给定一个整数数组，请将其重新排序，以构造最小值。
样例
给定[3,32,321],通过将数组重新排序，可构造6个可能性的数字：
3+32+321=332321
3+321+32=332132
32+3+321=323321
32+321+3=323213
321+3+32=321332
321+32+3=321323其中，最小值为 321323，所以，将数组重新排序后，该数组变为 [321, 32, 3]。
挑战
在原数组上完成，不使用额外空间。
分析：
问题的关键在于如何比较两个数字的大小，将小的数字放在高位，将大的数字放在低位，构造的新数字就应当最小的。但此处比较数字大小不是一般的方式那种比较。比如比较321和3，首先321的从左数第一位是3，与单个数字3相等，那么接下来该怎么比较呢？如果把3放在高位，把321放在低位，那么组成的数字是3321，比把321放在高为构成的数字3213大，显然这里应该判断321比3小，怎么个小法？既然321第一位跟三相等，那么接着比较下一位，发现单个数字3已经到了最后一位，那么把321剩下的数字21和3来进行比较，发现2比3小，所以321小于3。按照这个思路，调用Collections.sort()函数，构造一个新的比较器，在比较器中实现上述比较方法。按位比较，显然需要将数字转换为字符串，这样比较容易提取各个位的数字。
Java算法实现
public class Solution {
/**
* @param nums n non-negative integer array
* @return a string
*/
public String minNumber(int[] nums) {
// Write your code here
List<String>list=new ArrayList<>();
for(int i=0;i<nums.length;i++){
//将所有数字转化为字符串
list.add(String.valueOf(nums[i]));
}
Collections.sort(list,new Comparator<String>() {
//新的比较器，实现新方式的大小比较
@Override
public int compare(String str1, String str2) {
// TODO Auto-generated method stub
int i=0;
for(i=0;i<str1.length()&&i<str2.length();i++){
if(str1.charAt(i)<str2.charAt(i)){
//如果当前位已经比较出了大小，直接返回比较结果
return -1;
}
else if(str1.charAt(i)>str2.charAt(i)){
return 1;
}
}
if(i==str1.length()&&i==str2.length()){
//已经比较到了两个字符串的结尾
return 0;
}
else{
if(i<str2.length()){
//还没有比较到str2的结尾，用str2剩下的字符与str1进行比较
return compare(str1, str2.substring(i));
}
else{
//同上理
return compare(str1.substring(i), str2);
}
}
}
});
//构造结果字符串
StringBuilder sb=new StringBuilder();
for(String str:list){
sb.append(str);
}
String res=sb.toString();
int i=0;
/* 如果输入为[0],输出需要为"0";如果输入为[0,0,0,0,0],输出也应该为"0";
如果输入为[0,0,0,1,2,3],输出应为"123"。
下面的循环对此进行处理；
i<res.length()-1 的控制目的就是为了应对输入为[0]的情况，此时不需要增长i
*/
while(res.charAt(i)=='0'&&i<res.length()-1){
i++;
}
return res.substring(i);
}
}标记为Easy，难度确实不大。但是一般很难考虑周全，最后剔除前首 '0' 的步骤，如果不是提交失败收到提醒，则很难有人直接就考虑明白。