题目地址：https://leetcode.com/problems/lexicographical-numbers/description/
题目描述：
Given an integer n, return 1 - n in lexicographical order.
Forexample, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.
题目大意
给了一个数字n,找出1～n的所有数字的字典序排列。
解题方法
题目中说了输入可能是5百万，那么只能用O(N)的时间复杂度。
这个题的思路我是参考的Lexicographical Numbers 字典顺序的数字open in new window，不太好想。
1、 如果curr乘以10小于等于n，那么下个数字应该是curr末尾补0；
2、 如果curr已经到达了n，那么说明各位数字已经到头了，应该变化十位数字了，所以除以10，再加一这时可能会出现恰好进位的情况，而字典序可能是从末尾没有0的数字开始的，所以要把末尾的0去掉；
比如n=300时，会有这个队列1,10,100,101,102...198,199,2,20,200,201...299,3,30,300
代码如下：
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发