LeetCode——字典序排数

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

例如，
给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。

A：
1.第一想法是用map，map的key是转换成的String，value按顺序放置

    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>();
        int len = String.valueOf(n).length();//n的长度
        Map<String, ArrayList<Integer>> map = new TreeMap<>();
        for (int i = 1; i <= n; i++) {
            StringBuilder s = new StringBuilder(String.valueOf(i));
            while (s.length() < len) {
                s.append(0);//后面填充0
            }
            String s1 = s.toString();
            if (map.containsKey(s1)) {
                ArrayList<Integer> curr = map.get(s1);
                curr.add(i);
                map.put(s1, curr);
            } else {
                ArrayList<Integer> curr = new ArrayList<>();
                curr.add(i);
                map.put(s1, curr);
            }

        }
        for (ArrayList<Integer> curr : map.values()) {
            res.addAll(curr);
        }
        return res;
    }

后来我也考虑用每个值的头做key，但这样做顺序是错的。字典序中，顺序是1,10,100,11，但如果用头做key，顺序是1,10,11,……,19,100
但这个方法，肉眼可见，内存消耗极大。

2.递归解法，实则是十叉树前序遍历

    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>();
        dfs(0, n, res);//k是当前值
        return res;
    }

    private void dfs(int k, int n, List<Integer> res) {
        if (k > n)
            return;
        if (k != 0)
            res.add(k);
        for (int i = 0; i <= 9; i++) {
            int next = k * 10 + i;
            if (next > 0) {
                dfs(next, n, res);
            }
        }
    }