描述

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

注意事项

The result may be very large, so you need to return a string instead of an integer.

样例

给定 [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]。

挑战

在原数组上完成，不使用额外空间。

思路

重写 compare 方法

代码

public class Solution {
    /**
     * @param nums n non-negative integer array
     * @return a string
     */
    public String minNumber(int[] nums) {
        int n = nums.length;
        if (n < 1) {
            return "";
        }
        
        String[] strs = new String[n];
        for (int i = 0; i < n; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        
        Arrays.sort(strs, new Cmp());
        
        String ans = "";
        // 从大到小排列后，要求最小数必须从末尾开始取值拼接
        for (int i = n - 1; i >= 0; i--) {
            ans = ans.concat(strs[i]);
        }
        
        // 输入数字一部分为 0 的情况
        int i = 0;
        while (i < n && ans.charAt(i) == '0') {
            i++;
        }

        // 输入数字全部为 0 的情况
        if (i == n) {
            return "0";
        }
        return ans.substring(i);
    }
}

// 重写排序方法，如果 ba 大于 ab 则交换 a b 顺序，排序为从大到小排列
class Cmp implements Comparator<String>{
    @Override
    public int compare(String a, String b) {
        String ab = a.concat(b);
        String ba = b.concat(a);
        return ba.compareTo(ab);
    }
}