leetcode20220418打卡 - 386. 字典序排数[

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