跳转至

440. 字典序的第K小数字

题目描述

给定整数 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 <= 109

解法

方法一：字典树计数 + 贪心构造

本题要求在区间 \([1, n]\) 中，按字典序排序后，找到第 \(k\) 小的数字。由于 \(n\) 的范围非常大（最多可达 \(10^9\)），我们无法直接枚举所有数字后排序。因此我们采用贪心 + 字典树模拟的策略。

我们将 \([1, n]\) 看作一棵 十叉字典树（Trie）：

  • 每个节点是一个前缀，根节点为空串；
  • 节点的子节点是当前前缀拼接上 \(0 \sim 9\)；
  • 例如前缀 \(1\) 会有子节点 \(10, 11, \ldots, 19\)，而 \(10\) 会有 \(100, 101, \ldots, 109\)；
  • 这种结构天然符合字典序遍历。
根
├── 1
│   ├── 10
│   ├── 11
│   ├── ...
├── 2
├── ...

我们使用变量 \(\textit{curr}\) 表示当前前缀，初始为 \(1\)。每次我们尝试向下扩展前缀，直到找到第 \(k\) 小的数字。

每次我们计算当前前缀下有多少个合法数字（即以 \(\textit{curr}\) 为前缀、且不超过 \(n\) 的整数个数），记作 \(\textit{count}(\text{curr})\)：

  • 如果 \(k \ge \text{count}(\text{curr})\)：说明目标不在这棵子树中，跳过整棵子树，前缀右移：\(\textit{curr} \leftarrow \text{curr} + 1\)，并更新 \(k \leftarrow k - \text{count}(\text{curr})\)；
  • 否则：说明目标在当前前缀的子树中，进入下一层：\(\textit{curr} \leftarrow \text{curr} \times 10\)，并消耗一个前缀：\(k \leftarrow k - 1\)。

每一层我们将当前区间扩大 \(10\) 倍，向下延伸到更长的前缀，直到超出 \(n\)。

时间复杂度 \(O(\log^2 n)\)，空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        def count(curr):
            next, cnt = curr + 1, 0
            while curr <= n:
                cnt += min(n - curr + 1, next - curr)
                next, curr = next * 10, curr * 10
            return cnt

        curr = 1
        k -= 1
        while k:
            cnt = count(curr)
            if k >= cnt:
                k -= cnt
                curr += 1
            else:
                k -= 1
                curr *= 10
        return curr

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    private int n;

    public int findKthNumber(int n, int k) {
        this.n = n;
        long curr = 1;
        --k;
        while (k > 0) {
            int cnt = count(curr);
            if (k >= cnt) {
                k -= cnt;
                ++curr;
            } else {
                --k;
                curr *= 10;
            }
        }
        return (int) curr;
    }

    public int count(long curr) {
        long next = curr + 1;
        long cnt = 0;
        while (curr <= n) {
            cnt += Math.min(n - curr + 1, next - curr);
            next *= 10;
            curr *= 10;
        }
        return (int) cnt;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int n;

    int findKthNumber(int n, int k) {
        this->n = n;
        --k;
        long long curr = 1;
        while (k) {
            int cnt = count(curr);
            if (k >= cnt) {
                k -= cnt;
                ++curr;
            } else {
                --k;
                curr *= 10;
            }
        }
        return (int) curr;
    }

    int count(long long curr) {
        long long next = curr + 1;
        int cnt = 0;
        while (curr <= n) {
            cnt += min(n - curr + 1, next - curr);
            next *= 10;
            curr *= 10;
        }
        return cnt;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func findKthNumber(n int, k int) int {
    count := func(curr int) int {
        next := curr + 1
        cnt := 0
        for curr <= n {
            cnt += min(n-curr+1, next-curr)
            next *= 10
            curr *= 10
        }
        return cnt
    }
    curr := 1
    k--
    for k > 0 {
        cnt := count(curr)
        if k >= cnt {
            k -= cnt
            curr++
        } else {
            k--
            curr *= 10
        }
    }
    return curr
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function findKthNumber(n: number, k: number): number {
    function count(curr: number): number {
        let next = curr + 1;
        let cnt = 0;
        while (curr <= n) {
            cnt += Math.min(n - curr + 1, next - curr);
            curr *= 10;
            next *= 10;
        }
        return cnt;
    }

    let curr = 1;
    k--;

    while (k > 0) {
        const cnt = count(curr);
        if (k >= cnt) {
            k -= cnt;
            curr += 1;
        } else {
            k -= 1;
            curr *= 10;
        }
    }

    return curr;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
impl Solution {
    pub fn find_kth_number(n: i32, k: i32) -> i32 {
        fn count(mut curr: i64, n: i32) -> i32 {
            let mut next = curr + 1;
            let mut total = 0;
            let n = n as i64;
            while curr <= n {
                total += std::cmp::min(n - curr + 1, next - curr);
                curr *= 10;
                next *= 10;
            }
            total as i32
        }

        let mut curr = 1;
        let mut k = k - 1;

        while k > 0 {
            let cnt = count(curr as i64, n);
            if k >= cnt {
                k -= cnt;
                curr += 1;
            } else {
                k -= 1;
                curr *= 10;
            }
        }

        curr
    }
}

评论