将数组重新排序以构造最小值

题目描述

给定一个整数数组，请将其重新排序，以构造最小值。

样例

给定[3,32,321],通过将数组重新排序，可构造6个可能性的数字：

3+32+321=332321  3+321+32=33213232+3+321=32332132+321+3=323213321+3+32=321332321+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
    
     list=new ArrayList<>();        for(int i=0;i
     
      () {            //新的比较器，实现新方式的大小比较            @Override            public int compare(String str1, String str2) {                // TODO Auto-generated method stub                int i=0;                for(i=0;i
      
       
        str2.charAt(i)){                        return 1;                    }                }                if(i==str1.length()&&i==str2.length()){                    //已经比较到了两个字符串的结尾                    return 0;                }                else{                    if(i
       
      
     
    

标记为Easy，难度确实不大。但是一般很难考虑周全，最后剔除前首 '0' 的步骤，如果不是提交失败收到提醒，则很难有人直接就考虑明白。