剑指 Offer - 32 - 把数组排成最小的数

Question

题目

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

解析

这题关键是找到一个排序规则。然后数组根据这个规则排序就能排成一个最小的数字。

也就是是给出两个数字 a 和 b，我们需要确定一个规则判断 a 和 b 哪个应该排在前面，而不是仅仅比较这两个数字的值哪个更大。

如果只看长度不行，但是只看数字大小也不行。但是如果我们限定长度相同呢?

• 根据题目的要求，两个数字 a 和 b 能拼接成数字 ab 和 ba(此时 ab 和 ba 位数长度相同)。如果 ab<ba ，那么我们应该打印出 ab，也就是 a 应该排在 b 的前面，我们定义此时 a 小于 b；(若 ab < ba 则 a < b )
• 反之，如果 ba<ab ，我们定义 b 小于 a。 (若 ab > ba 则 a > b )
• 如果 ab=ba ，a 等于 b。(若 ab = ba 则 a = b )

如果直接用数字去拼接 nm，可能会溢出。但是我们可以直接用字符串拼接，然后定义字符串的比较规则即可。

举个例子:

• a = "3"、b = "31" ，不能简单的将 a 放在 b 的前面，
• 而是因为 331 > 313 ( ab > ba )，应该将 b 放在 a 的前面；

代码如下:

import java.util.*;

public class Solution {
    public String PrintMinNumber(int[] numbers) {
        ArrayList<String> list = new ArrayList<>();
        for (int i = 0; i < numbers.length; i++)
            list.add(numbers[i] + "");
        Collections.sort(list, (o1, o2) -> {
            return (o1 + o2).compareTo(o2 + o1);  //按照降序排列（第一个大于第二个返回 1-->升序排列)
        });
        StringBuilder res = new StringBuilder();
        for (String s : list)
            res.append(s);
        return res.toString();
    }
}

也可以用字符串数组排序:

import java.util.Arrays;

public class Solution {
    public String PrintMinNumber(int[] numbers) {
        int n = numbers.length;
        String[] str = new String[n];
        for (int i = 0; i < n; i++)
            str[i] = String.valueOf(numbers[i]);
        Arrays.sort(str, (s1, s2) -> (s1 + s2).compareTo(s2 + s1));
        StringBuilder res = new StringBuilder();
        for (String s : str)
            res.append(s);
        return res.toString();
    }
}