LeetCode 668. 乘法表中第k小的数

约 5 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 字节 百度
标签
数学 二分查找

题目描述

✅ 668. 乘法表中第k小的数

image-20260928224458379

image-20260928224458380

题意分析

乘法表第 $i$ 行、第 $j$ 列的值为 $i\times j$，行列下标从 $1$ 开始。把全部 $mn$ 个格子的值排序后，求第 $k$ 项；相同数值出现在不同格子中，也要分别占据名次。

解法：值域二分 + 每行计数

核心思路

[!blue]

不直接生成乘法表，而是对答案的数值二分。给定阈值 $x$，令 $C(x)$ 表示表中不超过 $x$ 的元素个数。第 $i$ 行的元素是 $i,2i,\ldots,ni$，满足 $ij\le x$ 的列数为 $\lfloor x/i\rfloor$，但最多只有 $n$ 列，所以这一行贡献 $\min(n,\lfloor x/i\rfloor)$。

将各行贡献相加就得到 $C(x)$，并且 $x$ 越大，计数不会减少。设第 $k$ 小的数为 $a$：当 $x<a$ 时，不超过 $x$ 的项不足 $k$ 个；当 $x\ge a$ 时，至少已有 $k$ 个。因此答案正是第一个满足 $C(x)\ge k$ 的整数阈值。

搜索区间初始化为 [1, m*n]。若 C(mid) >= k，答案不大于 mid，令 right = mid；否则答案严格大于 mid，令 left = mid + 1。每次既保留答案又缩小区间，最终两端重合就是最小可行阈值。

重复值会使计数一次跳过多个名次，所以不能要求恰好等于 $k$；即使计数恰好为 $k$，当前阈值也可能只是两个表中数值之间的空档，仍要继续寻找左边界。计数只在遇到真实表中元素时增加，因此最终首次达到 $k$ 的阈值一定就是某个格子的值。

解题步骤

  1. 令 left = 1、right = m * n，中点按 left + (right-left)/2 计算。
  2. 枚举所有行，把 min(n, mid / i) 累加到计数，整除自动向下取整。
  3. 根据计数是否至少为 k 更新边界，继续处理直到 left == right。
  4. 返回唯一剩余值。只有一个格子时无需进入循环；k = 1 和 k = m*n 也由相同边界逻辑处理。

代码实现

class Solution {
    // 值 x 作为阈值时，可以快速算出表中有多少个数不超过 x，用这个计数函数做二分查找。
    public int findKthNumber(int m, int n, int k) {
        long left = 1;
        long right = (long) m * n;

        while (left < right) {
            long mid = left + (right - left) / 2;

            // 重复值使计数跳跃，寻找首次达到名次的阈值
            if (countLE(mid, m, n) >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return (int) left;
    }

    private long countLE(long x, int m, int n) {
        long total = 0;

        for (int i = 1; i <= m; i++) {
            // 第 i 行按倍数计数，但最多只有 n 列
            total += Math.min(n, (int) (x / i));

            if (total > Integer.MAX_VALUE) {
                return Integer.MAX_VALUE;
            }
        }

        return total;
    }
}

func findKthNumber(m int, n int, k int) int {
    // 值 x 作为阈值时，可以快速算出表中有多少个数不超过 x，用这个计数函数做二分查找。
    left := int64(1)
    right := int64(m) * int64(n)
    for left < right {
        mid := left + (right-left)/2
        // 重复值使计数跳跃，寻找首次达到名次的阈值
        if countLE(mid, m, n) >= int64(k) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return int(left)
}

func countLE(x int64, m int, n int) int64 {
    var total int64
    for i := 1; i <= m; i++ {
        // 第 i 行按倍数计数，但最多只有 n 列
        c := int(x / int64(i))
        if c > n {
            c = n
        }
        total += int64(c)
    }
    return total
}

复杂度分析

  • 时间复杂度：$O(m\log(mn+1))$，每轮二分按行计数。
  • 空间复杂度：$O(1)$，表格不物化。

关键点总结

[!green]

  • 每行最多 n 项，整除结果必须截断到列数。
  • 计数允许跳过 k，判定用达到或超过。

易错点总结

[!yellow]

  • 按不同值去重，会改变重复元素的名次。
  • 每行不截断，会计入不存在的列。
  • 可行时直接排除中点，会漏掉刚好等于答案的候选。
  • 计数等于 k 就返回中点，可能返回表中根本不存在的值；仍需查找最小可行阈值。

相似题目

题目 难度 关联与区别
378. 有序矩阵中第 K 小的元素 中等 乘法表是隐式行列有序矩阵，本题可直接按每行商值计数，不必实际创建矩阵。
719. 找出第 K 小的数对距离 困难 按截止值统计不大于候选的数量以二分第 k 小；本题按乘法表的每行计数，该题排序后用双指针统计不超过候选的数对距离。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/leetcode-668
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！