LeetCode题练习与总结：字典序的第 K 小数字--440

一、题目描述

给定整数 n 和 k，返回  [1, n] 中字典序第 k 小的数字。

示例 1:

输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。

示例 2:

输入: n = 1, k = 1
输出: 1

提示:

• 1 <= k <= n <= 10^9

二、解题思路

这个问题可以通过模拟字典序的生成过程来解决。字典序生成过程类似于十叉树的遍历过程，每个节点有10个子节点（0-9）。我们可以使用深度优先搜索（DFS）来模拟这个过程。

以下是解题步骤：

1. 计算以某个数字 prefix 为前缀的数字的个数。例如，以1为前缀的数字有 [1, 10, 11, …, 19, 100, 101, …, 199, …]，直到数字不超过 n。

2. 使用一个计数器来记录已经遍历过的数字的个数。

3. 从1开始，对每个数字进行DFS，计算以该数字为前缀的数字个数。如果这个个数大于或等于 k，那么第 k 个数字一定在这个前缀下；否则，将计数器加上这个前缀下的数字个数，并继续下一个数字的DFS。

4. 当计数器的值等于 k 时，当前的数字就是我们要找的数字。

三、具体代码

class Solution {
    public int findKthNumber(int n, int k) {
        int prefix = 1;
        k--; // 因为从1开始，所以k需要减1
        while (k > 0) {
            int count = count(prefix, n);
            if (count <= k) {
                // 如果当前前缀下的数字个数小于k，说明第k小的数字不在这个前缀下
                // 将计数器减去当前前缀下的数字个数，并移动到下一个前缀
                k -= count;
                prefix++;
            } else {
                // 如果当前前缀下的数字个数大于或等于k，说明第k小的数字在这个前缀下
                // 将计数器减1（因为prefix本身也是其中一个数字），并深入到下一个前缀
                k--;
                prefix *= 10;
            }
        }
        return prefix;
    }

    // 计算以prefix为前缀的数字的个数
    private int count(int prefix, int n) {
        long cur = prefix;
        long next = cur + 1;
        int count = 0;
        while (cur <= n) {
            count += Math.min(n + 1, next) - cur;
            cur *= 10;
            next *= 10;
        }
        return count;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• 在findKthNumber方法中，我们有一个while循环，该循环的迭代次数依赖于k的值。每次迭代中，我们都会调用count方法。

• 在count方法中，我们有一个while循环，其迭代次数依赖于prefix的大小以及n的值。在每次迭代中，我们通过乘以10来计算以prefix为前缀的数字的数量。这个循环的迭代次数是O(log(n)/log(10))，因为当cur超过n时，循环会停止。这实际上就是O(log(n))，因为log(10)是一个常数。

• 在最坏的情况下，我们需要对每个前缀调用count方法，直到找到第k小的数字。在最坏的情况下，我们可能需要遍历所有前缀，直到我们达到n。因此，最坏情况下的时间复杂度是O(log(n)) * O(log(n))，即O(log^2(n))。

2. 空间复杂度

• 在findKthNumber方法中，我们使用了几个整型变量（prefix, k, count），这些变量占用的空间是常数级的，即O(1)。

• 在count方法中，我们也使用了几个整型变量（cur, next, count），同样这些变量占用的空间也是常数级的，即O(1)。

• 由于方法调用是迭代的，而不是递归的，我们不需要额外的空间来存储调用栈。因此，整个算法的空间复杂度是O(1)。

五、总结知识点

• 类定义与成员方法：

  • class Solution：定义了一个名为Solution的类。
  • public int findKthNumber(int n, int k)：定义了一个公共方法findKthNumber，接受两个整数参数n和k，并返回一个整数。

• 基本数据类型：

  • int：表示整数类型，用于定义变量和返回值。

• 控制结构：

  • while循环：用于在不确定迭代次数的情况下重复执行代码块。
  • if-else语句：用于条件判断，根据不同的条件执行不同的代码块。

• 数学运算：

  • 算术运算符：+、-、*用于基本的算术运算。
  • Math.min：用于计算两个数中的最小值。

• 逻辑运算：

  • long类型的使用：当整数可能超出int类型的范围时，使用long类型来避免溢出。

• 递归与迭代：

  • 迭代方法：代码通过迭代而不是递归来遍历数字前缀，避免了栈溢出的风险。

• 方法重载与封装：

  • private int count(int prefix, int n)：定义了一个私有方法count，用于计算以特定前缀开头的数字数量，这是代码封装的一个例子。

• 变量作用域：

  • 局部变量：在方法内部定义的变量（如prefix, k, count, cur, next）仅在方法内部有效。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。