20220418打卡： 字典序排数
题目描述
给你一个整数 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 * 104
解题思路：
题目要求设计一个时间复杂度为 O(n)且使用 O(1)额外空间的算法，因此我们不能使用直接排序的方法。
那么对于一个整数 number，它的下一个字典序整数对应下面的规则：
- 尝试在 number后面附加一个零，即
number * 10，如果number * 10 ≤ n，那么说明
number×10是下一个字典序整数； - 如果
number % 10 = 9或number + 1 > n，那么说明末尾的数位已经搜索完成，退回上一位，即number = number / 10，然后继续判断直到number / 10 ≠ 9且number + 1 ≤ n为止，那么number + 1是下一个字典序整数。
字典序最小的整数为number = 1，我们从它开始，然后依次获取下一个字典序整数，加入结果中，结束条件为已经获取到 n 个整数。
Swift解题代码：
static func lexicalOrder(_ n: Int) -> [Int] {
var data = Array<Int>()
var number = 1
var i = 0
while i < n {
data.append(number)
if number * 10 <= n {
// 处理 10、100、1000...
number *= 10
} else {
// 到尾数为9时，或者+1大于指定的数时，表示需要从下一个低位开始了
while number % 10 == 9 || number + 1 > n {
// 向下取整
number = Int(floor(Double(number) / 10.0))
}
number += 1
}
// 开始下一个循环
i += 1
}
return data
}
原题链接：https://leetcode-cn.com/problems/lexicographical-numbers
