算法：字典序排序

题目

给定一个整数n，返回从1到n的字典顺序。

示例

给定n=13，返回[1,10,11,12,13,2,3,4,5,6,7,8,9]。

请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据n小于等于5,000,000。

方法一

转成String后使用String的compare方法，再转回Integer。

public List<Integer> lexicalOrder(int n) {
    ArrayList<String> list = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
        list.add(String.valueOf(i));
    }
    Collections.sort(list);

    ArrayList<Integer> integers = new ArrayList<>();
    for (String s : list) {
        integers.add(Integer.valueOf(s));
    }
    return integers;
}

执行用时：27 ms, 在所有Java提交中击败了20.16%的用户 内存消耗：44.3 MB, 在所有Java提交中击败了41.82%的用户

方法二

数字1进入dfs递归后，判断不大于n则加入List，再对1乘以10后，对11到19做递归判断，如果大于n则跳出递归，不大于则11再乘以10`继续递归。

数字2到9以此类推。

public List<Integer> lexicalOrder2(int n) {
    List<Integer> list = new ArrayList<>(n);
    for (int i = 1; i <= 9; i++) {
        // list=empty, n=13, i=1
        dfs(list, n, i);
    }
    return list;
}

public boolean dfs(List<Integer> list, int n, int target) {
    // target=1 < n=13
    if (target > n) {
        return false;
    }
    // list={1}
    list.add(target);

    // target=10
    target *= 10;

    // 10 11 12 ... 19
    for (int i = 0; i <= 9; i++) {
        // list={1}, n=13, target+i=10+1=11
        if (!dfs(list, n, target + i)) {
            break;
        }
    }
    return true;
}

执行用时：3 ms, 在所有Java提交中击败了85.44%的用户 内存消耗：44.4 MB, 在所有Java提交中击败了33.65%的用户

LeetCode 原题地址

https://leetcode-cn.com/problems/lexicographical-numbers