LeetCode中等题之字典序排数

题目

给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。
示例 1：
输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]
示例 2：
输入：n = 2
输出：[1,2]
提示：
1 <= n <= 5 * 10^4
来源：力扣（LeetCode）

解题思路

  这个题目相对来说在中等题里面是比较简单的，先来说一下什么是字典序。字典序，故名思意，不管是在我们查阅汉语词典也好还是英语牛津词典也好，他都是按一定的字母顺序来排序，以英语词典为例，通常按照26个英文字母从a到z进行排序排版。而在同一个字母索引下，你会发现先是出现较短的英文单词，然后再慢慢出现较长的英文单词，而这些单词之间也是有一定的规律的，相同长度的单词之间它们的前面很长一部分大概率是重合的不一样的地方仅仅只在单词的尾部，而不一样的地方也是以a-z来排序的，这样递归的按照相应的顺序来拍完整整个词典的方式就是字典序。在计算机领域整个顺序一般而言是以ASCll码的大小来决定的通常大写字母在小写字母的前面其ASCll的值更小，对于本题的数字而言则相对顺序就是其本身的值的大小，后续的排序也类似于字典中的排序一致“先短再长，先小再大”，有了这样的提示，基于python的处理，我们可以直接先将数列的每个元素转化成str类型，然后排序，待排完序之后再转化成整数。

class Solution:def lexicalOrder(self, n: int) -> List[int]:return [int(j) for j in sorted([str(i) for i in range(1,n+1)])]