原题链接

描述

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

示例

输入：[3,32,321]
返回值："321323"

思路

DFS，和JZ27 字符串的排列一样的思想，如果直接暴力枚举的话很难而且是时间复杂度是阶乘级。使用 min 保存当前最小量，每次搜索到 numbers.length - 1 时到达尽头，把一路遍历的数字和 min 比较 更新 min 使其永远是最小值。

解答

public class Solution {
    int c;
    String res = "";
    String min = "z";

    // dfs,选出每个元素排列的结果,每排完一组就和min进行比较
    public String PrintMinNumber(int[] numbers) {
        if(numbers.length==0)return "";
        c = numbers.length;
        dfs(0, numbers);
        return min;
    }

    private void dfs(int x, int[] numbers) {
        if (x == c - 1) {
            for (int a : numbers) {
                res += a;
            }
            min = res.compareTo(min) > 0 ? min : res;
            // long tmp = Integer.valueOf(res) < Integer.valueOf(min) ?
            //         Integer.valueOf(res) : Integer.valueOf(min);
            res = "";
            return;
        }

        for (int i = x; i < c; i++) {
            swap(i, x, numbers);
            dfs(x + 1, numbers);
            swap(i, x, numbers);
        }
    }

    private void swap(int a, int b, int[] numbers) {
        int tmp = numbers[a];
        numbers[a] = numbers[b];
        numbers[b] = tmp;
    }

}

JZ32 把数组排成最小的数