Leetcode-386 dictionary order

subject Give you an integer  n , Returns the range in dictionary order  [1, n]  All integers in .

You have to design a time complexity of O(n) And the use of O(1) Extra space algorithm .

Example 1：

 Input ：n = 13
 Output ：[1,10,11,12,13,2,3,4,5,6,7,8,9]

---

If time complexity and space complexity are not considered, brainless operation can be used

        The first 1-n Convert integer to string type , Then sort and add to list in

Code ：

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);  // First convert the integer to string type 
        Arrays.sort(str); // Sort by dictionary order 
        List<Integer> list = new ArrayList<>();
        for(int i = 0;i<n;i++)
            list.add(Integer.valueOf(str[i]));
        return list;
    }
}

---

If time and space complexity are taken into account

To use    DFS （ This algorithm has not been mastered yet ）

recursive dfs

Multi order tree traversal similar to dictionary tree , The root node is 0, To be skipped , From the second floor 1-9 Start

Every node has 0-9  10 Nodes                     Here's the picture

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); // Start from left to right 
    }
}

---

Although the above recursion is convenient , But because recursion uses stacks , Spatial complexity is not O（1） All improvements

Use dfs iteration   In accordance with the spatial complexity 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)  // At the end of each node 
                    number=number/10; // If number=13  Next number=1
                number++;  //1+1=2  Start looking for 2 Child nodes of 
            }
        }
        return list;
    }
}