字典序排列

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return int整型一维数组
#
class Solution1:
    """
    题目：
        https://www.nowcoder.com/practice/de49cf70277048518314fbdcaba9b42c?tpId=196&tqId=40452&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        字符串排序
    复杂度：
        时间复杂度：O(nlogn)
        空间复杂度：O(n)
    """

    def orderArray(self, n):
        # write code here
        strNums = [str(i) for i in range(1, n + 1)]

        strNums.sort()

        return map(int, strNums)


class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/de49cf70277048518314fbdcaba9b42c?tpId=196&tqId=40452&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    参考：
        大神：唐喻铭
    算法：
        字典树
        初始：num = 1
        按照字典序规律：1 -> 10 -> 100 ...直到大于n时，从*10变为+1操作，这里需要注意的是：如果个位数是9，那么再+1，就需要进位，比如9 + 1 -> 2；或者num + 1 > n，也需要进位处理
        比如n = 28：
        1,10,11,12,13,...,19 下一个数组为2，而不是20
        1,10,11,...,19,2,20,21,...,28 下一个数字为3，而不是29
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O(1)
    """

    def orderArray(self, n):
        # write code here
        res, num = [], 1

        for i in range(n):
            res.append(num)
            if num * 10 <= n:
                num *= 10
            else:
                while num % 10 == 9&nbs***bsp;num + 1 > n:
                    num /= 10
                num += 1

        return res


if __name__ == "__main__":
    sol = Solution()

    # n = 5

    # n = 10

    n = 28

    res = sol.orderArray(n)

    print res