440. 字典序的第K小数字 : 计数模拟运用题

题目描述

这是 LeetCode 上的 440. 字典序的第K小数字 ，难度为 困难。

Tag : 「数学」、「模拟」、「找规律」、「计数」

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

示例 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^91<=k<=n<=109

计数模拟

寻找字典序第 kk 小的数。

我们可以将该过程分两步操作 :「确定前缀」和「从以某个前缀开始找目标值」。

假定我们存在某个函数 int getCnt(int x, int limit)，该函数实现了统计范围 [1, limit][1,limit] 内以 xx 为前缀的数的个数。

有了该函数之后，我们可以从最小的前缀 11 开始枚举，假设当前枚举到前缀 xx，根据 cnt = getCnt(x, n)cnt=getCnt(x,n) 与 kk 的大小关系进行分情况讨论：

• cnt < kcnt<k：说明所有以 xx 为前缀的数组均可跳过，此时让 xx 自增，kk 减去 cntcnt。含义为从下一个「数值比 xx 大」的前缀中找目标值；
• cnt \geqslant kcnt⩾k：说明目标值前缀必然为 xx，此时我们需要在以 xx 为前缀的前提下找目标值。此时让 xx 乘 1010，kk 减 11（代表跳过了 xx 本身）。含义为从下一个「字典序比 xx 大」的前缀中找目标值。

当 k = 1k=1 时，当前前缀 xx 即是答案（含义为以 xx 为前缀的所有数中，最小的数，也就是 xx 本身）。

然后重点看看 int getCnt(int x, int limit) 函数如何实现。

为了方便，记 xx 的位数为 nn，limitlimit 位数为 mm。

根据 getCnt 的函数定义，在范围 [1, limit][1,limit] 内，以 xx 为前缀的数值数量等于下面所有情况的数量之和：

• 位数为 nn 的数：仅有 xx 本身，共 11 个；
• 位数为 n + 1 < mn+1<m 的数，有 x0 到 x9，共 1010 个；
• 位数为 n + 2 < mn+2<m 的数，有 x00 到 x99，共 100100 个；
• ...
• 位数为mm的数，此时根据「limitlimit长度与xx等同的前缀uu」和「xx」的大小关系，进一步分情况讨论（举个 🌰，当limit = 12456limit=12456，xx为123123时，u = 124u=124，两者位数相差k = 2k=2位）：

• u < xu<x：此时所有位数为 mm 的数均大于 limitlimit，合法个数为 00；
• u == xu==x：此时所有位数为 mm 的数中部分满足 limitlimit 限制，合法个数为 limit - x * 10^k + 1limit−x∗10k+1 个；
• u > xu>x：此时所有位数为 mm 的数均小于 limitlimit，合法个数为 10^k10k。

代码：

class Solution {
    public int findKthNumber(int n, int k) {
        int ans = 1;
        while (k > 1) {
            int cnt = getCnt(ans, n);
            if (cnt < k) {
                k -= cnt; ans++;
            } else {
                k--; ans *= 10;
            }
        }
        return ans;
    }
    int getCnt(int x, int limit) {
        String a = String.valueOf(x), b = String.valueOf(limit);
        int n = a.length(), m = b.length(), k = m - n;
        int ans = 0, u = Integer.parseInt(b.substring(0, n));
        for (int i = 0; i < k; i++) ans += Math.pow(10, i);
        if (u > x) ans += Math.pow(10, k);
        else if (u == x) ans += limit - x * Math.pow(10, k) + 1;
        return ans;
    }
}
复制代码

• 时间复杂度：枚举前缀以及 getCnt 操作均与位数相关，复杂度均为 O(\log{n})O(logn)。整体复杂度为 O(\log{^2}{n})O(log2n)
• 空间复杂度：忽略子串生成复杂度为 O(1)O(1)，否则为 O(\log{^2}{n})O(log2n)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.440 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。