把数组排成最小的数

剑指 Offer 45. 把数组排成最小的数

难度：中等

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: "102"

示例 2:

输入: [3,30,34,5,9]
输出: "3033459"

提示:

• 0 < nums.length <= 100

说明:

• 输出结果可能非常大，所以你需要返回一个字符串而不是整数
• 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

排序规则

这道题其实是希望我们能找到一个排序规则，数组根据这个规则排序之后能排成一个最小的数字。要确定排序规则，就要比较两个数字，也就是给出两个数字m和n，我们需要确定一个规则判断m和n哪个应该排在前面，而不是仅仅比较这两个数字的值哪个更大。

根据题目的要求，两个数字 m 和 n 能拼接成数字 mn 和 nm。如果mn<nm，那么我们应该打印出mn，也就是m应该排在n的前面，我们定义此时m小于n；反之，如果nm<mn，我们定义n小于m。

class Solution {
    public String minNumber(int[] nums) {
        if (nums.length == 0) return "";
        String[] numStrs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            numStrs[i] = Integer.toString(nums[i]);
        }

        Arrays.sort(numStrs, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o1+o2).compareTo(o2+o1);         //定义排序规则，如果ab大于ba，那么ba这个组合应该较小的组合，因此b应该在a前面
            }
        });
        StringBuilder bd = new StringBuilder();
        for (int i = 0; i < numStrs.length; i++) {
            bd.append(numStrs[i]);
        }
        return bd.toString();
    }
}

赏

谢谢你请我吃糖果

微信