数组的字典排序

前端时间碰到一个题目很有趣，分享一下：

题目：给你一个不重复的无序整型数组nums，要求输出数组的字典排序

字典排序不是普通的排序，他需要对数字的每一位进行排序，
如无序数组：nums=[12, 14, 11, 39, 339, 345, 1, 2, 4, 555, 501, 45, 29, 23, 25]
输出字典序为：[1, 11, 12, 14, 2, 23, 25, 29, 339, 345, 39, 4, 45, 501, 555]

根据leetcode上面大神提供的1-n的数字典排序解法宫水三叶大神加以改造，就可以写出适合的解法

如上图，主要的思想是对多叉树进行进行递归，第一层根节点是0，可以省略；第二层是：1、2、3…9，第三层是两位数：10,11,12，。。。。19, 21,22,23.。。29，。。。。。。91,92，。。。99；第四层是三位数，100,101，。。。。109,110,111,112，。。。119，。。。190,191,192，。。。199；第五层是四位数，依次类推
详细代码如下：

public class ArrayToLexicalOrder {
    

    public static void main(String[] args) {
    
        System.out.println(arrayToLexicalOrder(new int[]{
    12, 14, 11, 39, 339, 345, 1, 2, 4, 555, 501, 45, 29, 23, 25}));
    }

    public static List<Integer> arrayToLexicalOrder(int[] nums) {
    
        // 获取最大的数
        int max = getMax(nums);
        List<Integer> resList = new ArrayList<>();
        // 数组转为List，方便后面判断使用
        List<Integer> targetList = Arrays.stream(nums).boxed().collect(Collectors.toList());
        // 递归个位开始
        for (int i = 1; i <= 9; i++) {
    
            dfs(i, max, targetList, resList);
        }
        return resList;
    }

    private static int getMax(int[] nums) {
    
        if (nums == null || nums.length == 0) return Integer.MIN_VALUE;
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
    
            if (max < nums[i]) max = nums[i];
        }
        return max;
    }

    private static void dfs(Integer cur, Integer max, List<Integer> targetList, List<Integer> resList) {
    
        // 设置最大值，超过了，意味着递归可以结束了
        if (cur > max) return;
        // 如果当前数字在列表中，加入到结果列表
        if (targetList.contains(cur)) resList.add(cur);
        // dfs以cur开头的各个数值（如cur=2，这里的递归范围是：20、21、22、23....29）
        for (int i = 0; i <= 9; i++) {
    
            dfs(cur * 10 + i, max, targetList, resList);
        }
    }
}

输出结果：