题目描述

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/lexicographical-numbers
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

所谓字典顺序就是假设n=103时,1,10,100,101,102,103,11,12,...,19,2,20,.....,89,9,91....99

通过观察汉语字典,我们可以知道如果按照拼音的规则,在前n-1为相同的情况下,通过对比第n位的大小,来对这个数进行排序。第n位大的放后面,小的放前面。这个数字也是相同的道理,在n刚开始小于n的时候,不断地将它扩大为原来的10倍,直到某次扩大十倍比n大了,就不再扩大,就要通过判断它+1后比n大还是+1后能被10整除,满足以上两个条件中的一个说明要对这个数字进行缩小十倍的调整,如果缩小10倍后仍然满足以上两个条件之一,还要继续缩小,直到缩至满足题意,将得到的数加一后继续下一趟循环;否则直接+1放入答案数组即可。这种方式有点类似于深度优先搜索,先从一个点不断地深入,等到没有可走的路径时,回退到还有未被访问结点的那一层,继续深度优先,直到所有的点都走过一遍。

代码

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