386. 字典序排数.md

386. 字典序排数

题目传送门

点击这里

解题思路

这道题其实有一个提示了，就是时间复杂度为 $O(n)$，一般来说很多人会选择自定义排序规则或者直接sort的方法，但是这里提示用 $O(n)$的时间复杂度方法，也就是一次遍历，那么使用一次遍历的方法就相当于在遍历的过程中将值添加到结果里，(可能是多次遍历，但对这道题的解答分析没有影响)，也就是我们要对每一个num进行判断，所以使用迭代的方法来做，dfs+前缀树。

代码

func lexicalOrder(n int) []int {
    res := make([]int, n)
    num := 1
    for i := range res {
        res[i] = num
        // 从1开始，乘10先加入结果，然后依次加入11、12...，所以我们每次要先判断一下num*10 <= n，之后每次num++，如果num%10 == 9 || num+1 > n，也就是到了19、29...要开始下一个字典序了或者是超出n的范围了，则num /= 10从新的字典序开始。
        if num*10 <= n {
            num *= 10
        } else {
            for num%10 == 9 || num+1 > n {
                num /= 10
            }
            num++
        }
    }
    return res
}