subject

Topic linking

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]

Example 2：

 Input ：n = 2
 Output ：[1,2]

Problem solving

Method 1 ： Dictionary tree + The former sequence traversal

class Trie{
    
public:
    bool isEnd=false;
    vector<Trie*> next=vector<Trie*>(10,nullptr);
};


class Solution {
    
public:
    Trie* trie=new Trie();
    vector<int> res;
    
    vector<int> lexicalOrder(int n) {
    
        for(int i=1;i<=n;i++){
    
            insert(to_string(i));
        }
        traversal(trie,0);
        return res;
    }

    // Pre order traversal of dictionary tree 
    void traversal(Trie* root,int path){
    
        if(root->isEnd){
    
            res.push_back(path);
        }
        for(int i=0;i<10;i++){
    
            if(root->next[i]){
    
                traversal(root->next[i],path*10+i);
            }
        }
    }

    // Dictionary tree insert node 
    void insert(string&& s){
    
        Trie* node=trie;
        for(char c:s){
    
            if(node->next[c-'0']==nullptr){
    
                node->next[c-'0']=new Trie();
            }
            node=node->next[c-'0'];
        }
        node->isEnd=true;
    }
};

Method 2 ： iteration

class Solution {
    
public:
    vector<int> lexicalOrder(int n) {
    
        vector<int> res(n);
        int num=1;
        for(int i=0;i<n;i++){
    
            res[i]=num;
            if(num*10<=n){
    
                num*=10;
            }else{
    
                while(num%10==9||num+1>n){
    
                    num/=10;
                }
                num++;
            }
        }
        return res;
    }
};