LeetCode 440. 字典序的第K小数字

Categories:

题目描述
思路分析
1. 解法一：字典序树遍历（推荐）
相似题目

题目描述

✅ 440. 字典序的第K小数字

思路分析

解法一：字典序树遍历（推荐）

核心思路：

将 [1, n] 中的所有整数按字典序排列，本质上是一棵以 1~9 为根的十叉树（每个节点的子节点是在其后追加 0~9）。

从当前前缀 cur 开始，通过 countSteps(n, cur, cur+1) 计算以 cur 为前缀的数字总数 steps。

若 steps <= k，说明第 k 小的数不在当前前缀下，跳到下一个前缀：cur++，k -= steps。

若 steps > k，说明第 k 小的数在当前前缀下，深入一层：cur *= 10，k--。

countSteps(n, cur, next) 通过逐层累加 [cur, next) 在 [1, n] 范围内的数字个数来计算前缀数量，每层 cur *= 10，next *= 10。

复杂度分析：

时间复杂度：O(log²n)，其中 n 是给定的上界。外层最多遍历 O(logn) 个前缀节点，每次 countSteps 调用需 O(logn) 次迭代，总计 O(log²n)。

空间复杂度：O(1)，只使用常数个辅助变量。

class Solution {
    public int findKthNumber(int n, int k) {
        int cur = 1;
        // k 初始减 1，因为 cur=1 本身占了第 1 个位置
        k--;
        while (k > 0) {
            // 计算以 cur 为前缀的数字总数
            long steps = countSteps(n, cur, cur + 1);
            if (steps <= k) {
                // 第 k 小不在当前前缀下，跳到下一个前缀
                k -= steps;
                cur++;
            } else {
                // 第 k 小在当前前缀下，深入一层
                k--;
                cur *= 10;
            }
        }
        return cur;
    }

    /**
     * 计算 [1, n] 中以 cur 为前缀的数字数量
     * 即统计字典序树中 cur 子树内的节点总数
     */
    private long countSteps(int n, long cur, long next) {
        long steps = 0;
        while (cur <= n) {
            // 当前层 [cur, min(next, n+1)) 范围内的数字数量
            steps += Math.min((long) n + 1, next) - cur;
            cur *= 10;
            next *= 10;
        }
        return steps;
    }
}

func findKthNumber(n int, k int) int {
    cur := 1
    // k 初始减 1，因为 cur=1 本身占了第 1 个位置
    k--
    for k > 0 {
        // 计算以 cur 为前缀的数字总数
        steps := countSteps(n, cur, cur+1)
        if steps <= k {
            // 第 k 小不在当前前缀下，跳到下一个前缀
            k -= steps
            cur++
        } else {
            // 第 k 小在当前前缀下，深入一层
            k--
            cur *= 10
        }
    }
    return cur
}

// countSteps 计算 [1, n] 中以 cur 为前缀的数字数量
func countSteps(n, cur, next int) int {
    steps := 0
    for cur <= n {
        // 当前层 [cur, min(next, n+1)) 范围内的数字数量
        end := next
        if n+1 < next {
            end = n + 1
        }
        steps += end - cur
        cur *= 10
        next *= 10
    }
    return steps
}

相似题目

题目	难度	考察点
386. 字典序排数	中等	字典序树、DFS
1163. 按字典序排在最后的子串	困难	字符串、双指针
212. 单词搜索 II	困难	字典树、回溯
208. 实现 Trie (前缀树)	中等	字典树
677. 键值映射	中等	字典树、前缀统计
472. 连接词	困难	字典树、动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/74730860