菜鸟扣代码第23天：leetcode第386题--字典序排数

题目描述：

给定一个整数 n, 返回从 1 到 n 的字典顺序。

例如，

给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。

请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/lexicographical-numbers

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码：

class Solution:
    def lexicalOrder(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        cur = 1
        ans = []
        for i in range(n):
            ans.append(cur)
            if cur * 10 <= n:
                cur *= 10
            else:
                if cur >= n:
                    cur //= 10
                cur += 1
                while cur % 10 == 0:
                    cur //= 10
        return ans
           

思路：

这个题目，想了半天没有思路，参考了论坛上别人的思路：

首先定义curr用来表示目前的数字，如果curr*10小于等于n，那么下个数字应该是curr0；如果curr已经到达n，则说明各位数字已经到头，所以除以10再加，。这时可能会出现恰好进位的情况，而字典序可能是从末尾没有0的数字开始的，所以要把末尾的0去掉。