386. Lexicographical Numbers 字典序排数
难度: 中等
刷题内容
原题连接
- https://leetcode.com/problems/lexicographical-numbers
- https://leetcode-cn.com/problems/lexicographical-numbers
内容描述
给定一个整数 n, 返回从 1 到 n 的字典顺序。
例如，
给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。
解题方案
思路 1
那当然是直接转换成string比较排序啊，多么暴力，简单明了, beats 66.87%
- 时间复杂度：O(NlogN)
- 空间复杂度：O(N)
class Solution(object):
def lexicalOrder(self, n):
"""
:type n: int
:rtype: List[int]
"""
return sorted(range(1, n+1), key=lambda x: str(x))
思路 2
其实我们每次只要知道下一个数是啥就行了
例如对于67这个数，
- 它的下一个数要么是670（如果670 <= n ）的话
- 要么是68（如果68 <= n ）的话, 同时还要注意，如果我们例子中n换成200的话，如果当前数字为199，那其实它的下一个数字应该是2而不是200，
所以这里我们要多加一个判断(cur + 1) % 10 != 0, 然后对于尾数是9的数字我们要一直除以10让它尾数不是9之后再加1，即199 --> 2的过程
- 要么是7（当然7肯定小于n了，因为67都出现了）
- 时间复杂度：O(N)
- 空间复杂度：O(1)
这个方法beats 94.59%
class Solution(object):
def lexicalOrder(self, n):
"""
:type n: int
:rtype: List[int]
"""
res = []
cur = 1
for i in range(n):
res.append(cur)
if (cur * 10 <= n):
cur *= 10
elif cur + 1 <= n and (cur + 1) % 10 != 0:
cur += 1
else:
while (cur/10) % 10 == 9:
cur /= 10
cur = cur / 10 + 1
return res
