字典序排数

说在前面

🎈今天给大家带来的是算法练习,题目为"字典序排数"。

问题描述

给你一个整数 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、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是 54321。

算法设计

知道了什么是字典序之后，我们就可以开始来设计我们的程序了，如下图：

我们期望的输出应该是这样的。
我们需要按顺序找出每一位置上的所有数字，如：

• 第1个数字

我们需要先找出所有个位数为1的数字

• 第2个数字

在个位数为1的数字中找出第二位数位0的数字
.
.
.

• 第n个数字

在个位数为1且其他位数的数字都为0的数字
每一个位置上的数字都需要进行以上的循环步骤，这么一看我们可以使用递归的方法来进行解题，但是题目要求必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法，所以我们改用迭代循环的方式来解题，具体代码如下：

AC代码

function lexicalOrder(n: number): number[] {
  const res = [];
  let num = 1;
  for (let i = 0; i < n; i++) {
    res.push(num);
    if (num * 10 <= n) {
      num *= 10;
    } else {
      while (num + 1 > n || num % 10 == 9) num = Math.floor(num / 10);
      num++;
    }
  }
  return res;
}

说在后面

🎉这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。