Medium

题目描述

给你一个整数 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]

提示：

  • 1 <= n <= 5 * 10^4

解题思路

这道题要求按字典序排列数字，关键在于理解字典序的规律。

思路分析：

字典序排列就是把数字当作字符串来排序。观察示例1的输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]，我们可以发现规律：

  • 从1开始
  • 优先考虑在当前数字后面添加0（即乘以10）
  • 如果添加0后超过n，则考虑加1
  • 如果当前数字的个位是9或者加1后超过n，则需要回退到上一层

算法实现：

可以用深度优先搜索(DFS)的思想，把数字看作树的节点：

  • 根节点为空
  • 第一层节点为1-9
  • 每个节点的子节点为在其后添加0-9得到的数字

更优雅的方法是直接模拟这个过程：

  1. 从1开始遍历
  2. 每次尝试在当前数字后加0（相当于乘10）
  3. 如果不能加0，就尝试加1
  4. 如果当前数字末位是9或超出范围，就需要除以10回到上一层，然后加1

这样可以做到O(n)时间复杂度和O(1)额外空间。

代码实现

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> result;
        int current = 1;
        
        for (int i = 0; i < n; i++) {
            result.push_back(current);
            
            if (current * 10 <= n) {
                current *= 10;
            } else {
                while (current % 10 == 9 || current >= n) {
                    current /= 10;
                }
                current++;
            }
        }
        
        return result;
    }
};

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        result = []
        current = 1
        
        for _ in range(n):
            result.append(current)
            
            if current * 10 <= n:
                current *= 10
            else:
                while current % 10 == 9 or current >= n:
                    current //= 10
                current += 1
        
        return result

public class Solution {
    public IList<int> LexicalOrder(int n) {
        var result = new List<int>();
        int current = 1;
        
        for (int i = 0; i < n; i++) {
            result.Add(current);
            
            if (current * 10 <= n) {
                current *= 10;
            } else {
                while (current % 10 == 9 || current >= n) {
                    current /= 10;
                }
                current++;
            }
        }
        
        return result;
    }
}

var lexicalOrder = function(n) {
    const result = [];
    let current = 1;
    
    for (let i = 0; i < n; i++) {
        result.push(current);
        
        if (current * 10 <= n) {
            current *= 10;
        } else {
            if (current >= n) {
                current = Math.floor(current / 10);
            }
            current++;
            while (current % 10 === 0) {
                current = Math.floor(current / 10);
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)恰好遍历n个数字，每个数字的处理时间为常数
空间复杂度O(1)只使用了常数级别的额外变量