Skip to content

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


回到顶部