386. Dictionary order (medium) - iteration - full arrangement

One 、 Title Description

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]

Two 、 Problem solving

iteration

share n The number needs to be processed , Suppose the number of currently processed data is j, According to the dictionary order rule , On the premise that the conditions are met , Our priority is j Add 0（ namely j * 10 < n Satisfy ）, Otherwise, we consider fallback the previous bit and add one .

class Solution {
    
    public List<Integer> lexicalOrder(int n) {
    
        // iteration 
        List<Integer> res = new ArrayList<>();
        int number = 1;
        for(int i = 0;i<n;i++){
    
            res.add(number);
            // First try at number Back plus 0
            if(number * 10 <= n){
    
                number *= 10;
            }else{
    
                // If added 0 Later is greater than n 了 , Then add only one at a time 1. Of course, you also need to judge whether to carry   such as 19,29,39... Reach the carry requirement and then go back to the previous bit .
                while( number % 10 == 9 || number+1>n){
    
                    number /= 10;
                }
                number++;
            }
        }
        return res;
    }
}

Time complexity ：O(n);

Spatial complexity ：O(1).