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

题目描述

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

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

示例 1:

1
2
3
4
5
输入: n = 13, k = 2

输出: 10

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

示例 2:
1
2
3
输入: n = 1, k = 1

输出: 1

提示:

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

计数模拟

寻找字典序第 $k$ 小的数。

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

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

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

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

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

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

为了方便，记 $x$ 的位数为 $n$，$limit$ 位数为 $m$。

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

  • 位数为 $n$ 的数：仅有 $x$ 本身，共 $1$ 个；
  • 位数为 $n + 1 < m$ 的数，有 x0 到 x9，共 $10$ 个；
  • 位数为 $n + 2 < m$ 的数，有 x00 到 x99，共 $100$ 个；
  • …
  • 位数为 $m$ 的数，此时根据「$limit$ 长度与 $x$ 等同的前缀 $u$」和「$x$」的大小关系，进一步分情况讨论（举个 🌰，当 $limit = 12456$，$x$ 为 $123$ 时，$u = 124$，两者位数相差 $k = 2$ 位）：
    • $u < x$：此时所有位数为 $m$ 的数均大于 $limit$，合法个数为 $0$；
    • $u == x$：此时所有位数为 $m$ 的数中部分满足 $limit$ 限制，合法个数为 $limit - x * 10^k + 1$ 个（只有 $[x0…0, limit]$ 为合法数）；
    • $u > x$：此时所有位数为 $m$ 的数均小于 $limit$，合法个数为 $10^k$。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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 = to_string(x), b = to_string(limit);
        int n = a.length(), m = b.length(), k = m - n;
        int ans = 0, u = stoi(b.substr(0, n));
        for (int i = 0; i < k; i++) ans += pow(10, i);
        if (u > x) ans += pow(10, k);
        else if (u == x) ans += limit - x * pow(10, k) + 1;
        return ans;
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        def get_cnt(x, limit):
            a, b = str(x), str(limit)
            n, m = len(a), len(b)
            k = m - n
            ans = 0
            u = int(b[:n])
            for i in range(k):
                ans += int(pow(10, i))
            if u > x:
                ans += int(pow(10, k))
            elif u == x:
                ans += limit - x * int(pow(10, k)) + 1
            return ans

        ans = 1
        while k > 1:
            cnt = get_cnt(ans, n)
            if cnt < k:
                k, ans = k - cnt, ans + 1
            else:
                k, ans = k - 1, ans * 10
        return ans

TypeScript 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function findKthNumber(n: number, k: number): number {
    const getCnt = function(x: number, limit: number): number {
        const a = String(x), b = String(limit);
        const n = a.length, m = b.length, k = m - n;
        let ans = 0;
        let u = parseInt(b.substring(0, n));
        for (let 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;
    };
    let ans = 1;
    while (k > 1) {
        let cnt = getCnt(ans, n);
        if (cnt < k) {
            k -= cnt; ans++;
        } else {
            k--; ans *= 10;
        }
    }
    return ans;
};

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

最后

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

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

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

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