0386._Lexicographical_Numbers.md

386. Lexicographical Numbers

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/lexicographical-numbers/description/

内容描述

Given an integer n, return 1 - n in lexicographical order.

For example, 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.

解题方案

思路 1 - 时间复杂度: O(NlgN)- 空间复杂度: O(N)******

那当然是直接转换成string比较排序啊，多么暴力，简单明了, beats 97.65%

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 - 时间复杂度: O(N)- 空间复杂度: O(1)******

其实我们每次只要知道下一个数是啥就行了 例如对于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都出现了）

这个方法beats 94.94%

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