leetcode 第386题 字典序排数 python解法
leetcode 第386题 字典序排数 python解法
问题分析
先看题目:
题目要求将整数按照字典序排序,一看到这个我先想到了字符串是按照字典序排序的。所以,先想的方法是先将所有的整数存到数组,然后全部转为字符串。接着对字符串数组进行排序,最后将字符串转为整形数组。这种方法思路很简单,而且容易写。但是这里用到了字符串的排序,所以有点投机取巧。另外,该方法的时间复杂度大于O(n)。
另一种方法是参考了别人的答案。
首先生成一个大小为n的列表,并全部赋值为0。接下来就只要将从1~n共n个数逐个填到数组中。现在的问题就是如何在每个位置上填上合适的数。
有一点是可以确定的,那就是第一个位置(如果存在的话)上一定是1。接下来做的就是根据当前的数推测出下一个位置上的数。而下一个位置的数有三种情况:1,当前的数乘上10;2,当前的数加上1;3,判断当前的数整除10后是否等于9,如果等于9,继续整除10,最后加上1。如果当前的数为n,那么直接执行第三项。 这三种方法依次判断,首先将数乘上10,这样就是在当前的数后面加一个0(即1后面紧接为10,100, 1000),这样的数是最接近当前的数。如果乘上10大于n时,马上就进行第二个条件,即每个数加一。加一是将最后一位上的数加一如(1001, 1002,···, 1009),这时的数是最接近当前数的。如果最后末位加到了9,最后进行第三个条件。将当前的数整除10,如果最后一位等于九,接着整除(如1999,整除10为19,得接着整除10,最后得到1,末尾不为9,接着加1, 为2)。这样就从首位为1到了首位为2。
按照上面的三种方法,可以逐渐将n个数逐渐填到数组中。
源码
class Solution:
def lexicalOrder(self, n):
"""
:type n: int
:rtype: List[int]
"""
# 投机取巧,用字符串
# return [int(i) for i in sorted([str(i) for i in range(1, n+1, 1)])]
# 这种方法比较好
ret = [0] * n
num = 1
for i in range(n):
ret[i] = num
# 计算下一个位置的num
if num * 10 <= n:
num *= 10
else:
while num % 10 == 9 or num == n:
num = num // 10
num += 1
return ret