386. 字典序排数(中等)-迭代-全排列

一、题目描述

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

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

示例 1：

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

示例 2：

输入：n = 2
输出：[1,2]

二、解题

迭代

共有 n 个数需要被处理，假设当前处理到的数为 j，根据字典序规则，在满足条件的前提下，我们优先在 j 的后面添加 0（即 j * 10 < n 满足），否则我们考虑将上一位回退并进行加一操作。

class Solution {
    
    public List<Integer> lexicalOrder(int n) {
    
        //迭代
        List<Integer> res = new ArrayList<>();
        int number = 1;
        for(int i = 0;i<n;i++){
    
            res.add(number);
            //首先尝试在number后面加0
            if(number * 10 <= n){
    
                number *= 10;
            }else{
    
                //如果加0后大于n了，则每次只加1.当然也需要判断是否进位 比如19,29,39。。。达到进位要求然后回退上一位。
                while( number % 10 == 9 || number+1>n){
    
                    number /= 10;
                }
                number++;
            }
        }
        return res;
    }
}

时间复杂度：O(n)；

空间复杂度：O(1)。