LeetCode-386 字典序排数

题目给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。

你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。

示例 1：

输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]

---

若不考虑时间复杂度和空间复杂度可以使用无脑操作

        先把1-n的整数转为string类型，然后排序再加入到list中

代码：

class Solution {
    public List<Integer> lexicalOrder(int n) {
        String[] str = new String[n];
        for(int i=0;i<n;i++)
            str[i]=String.valueOf(i+1);  //先将整数转为string类型
        Arrays.sort(str); //按字典序排序
        List<Integer> list = new ArrayList<>();
        for(int i = 0;i<n;i++)
            list.add(Integer.valueOf(str[i]));
        return list;
    }
}

---

若考虑到时间和空间复杂度

要使用   DFS （这个算法还没有掌握）

递归dfs

类似字典树的多阶树遍历，根节点为0，要被跳过，从第二层1-9开始

每一个节点有0-9  10个节点                    如下图

class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> lexicalOrder(int n) {
        for(int i=1;i<=9;i++)
            dfs(i,n);
        return list;
    }
    public void dfs(int cur,int limit){
        if(cur > limit)
            return;
        list.add(cur);
        for(int i=0;i<=9;i++)
            dfs(cur*10+i,limit); //从左到右开始找
    }
}

---

上述递归虽方便，但由于递归会使用栈，空间复杂度并不是O（1）所有改进一下

使用dfs迭代  符合空间复杂度O（1）

class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> list = new ArrayList<>();
        int number=1;
        for(int i=0;i<n;i++){
            list.add(number);
            if(number*10<=n)
                number=number*10;
            else{
                while(number%10==9||number+1>n)  //到了每一个节点的末尾
                    number=number/10; //如果number=13 则下一个number=1
                number++;  //1+1=2 开始找2的子节点
            }
        }
        return list;
    }
}