字典序排数

题目

给你一个整数 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=123，字典序应该是1,10,100,101,102，这里只做了两种操作，乘10和加1，那我们就要搞清楚以下两个问题：

• 什么时候乘10
• 什么时候加1

优先选择乘10（100的字典序小于11），直到乘10大于n为止；
如果当前值乘10会大于n，那我们就选择加1，加1需要考虑以下两个边界问题：

• 加1之后大于n
• 当前值的个位数是9

如果当前值加1之后大于n，如当前值为123，则要整除10之后进行加1；
如果当前值的个位数是9，如109加1之后变为110，而11的字典序小于110，则要整除10之后进行加1；

Python代码

class Solution:def lexicalOrder(self, n: int) -> List[int]:ans = [0] * nnum = 1for i in range(n):ans[i] = numif num * 10 <= n:num *= 10else:while num % 10 == 9 or num + 1 > n:num //= 10num += 1return ans

C代码

/*** Note: The returned array must be malloced, assume caller calls free().*/
int* lexicalOrder(int n, int* returnSize) {int *ans = (int *)malloc(n * sizeof(int));memset(ans, 0, n * sizeof(int));int num = 1;for (int i = 0; i < n; i++) {ans[i] = num;if (num * 10 <= n) {num = num * 10;} else {while (num % 10 == 9 | num + 1 > n) {num = num / 10;}num++;}}*returnSize = n;return ans;
}

复杂度

• 时间复杂度O(N)
• 空间复杂度O(1)