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
回到顶部