How do I find the kth smallest number in the multiplication table?

Use binary search on the answer space, counting how many elements are smaller than or equal to the current mid value. Adjust the search range accordingly until you find the kth smallest element.

What is the time complexity of solving this problem?

The time complexity is O(m * log(m * n)) due to binary search over the range [1, m * n] and counting elements less than or equal to mid in each row, which takes O(m).

Can I solve the Kth Smallest Number in Multiplication Table without binary search?

While it's theoretically possible to use brute force or other methods, binary search is the most efficient approach for this problem, especially for larger values of m and n.

How does binary search help in this problem?

Binary search optimizes the search for the kth smallest element by reducing the answer space progressively, making the solution more efficient than brute force methods.

What are the constraints of the Kth Smallest Number in Multiplication Table problem?

The constraints are 1 <= m, n <= 3 * 10^4 and 1 <= k <= m * n, meaning that the solution must be efficient enough to handle large input sizes.

#668

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

乘法表中第k小的数

几乎每一个人都用乘法表。但是你能在乘法表中快速找到第 k 小的数字吗？乘法表是大小为 m x n 的一个整数矩阵，其中 mat[i][j] == i * j （下标从 1 开始）。给你三个整数 m 、 n 和 k ，请你在大小为 m x n 的乘法表中，找出并返回第 k 小的数字。示例 1…

数学二分查找

题目描述

几乎每一个人都用乘法表。但是你能在乘法表中快速找到第 k 小的数字吗？

乘法表是大小为 m x n 的一个整数矩阵，其中 mat[i][j] == i * j（下标从 1 开始）。

给你三个整数 m、n 和 k，请你在大小为 m x n 的乘法表中，找出并返回第 k 小的数字。

示例 1：

输入：m = 3, n = 3, k = 5
输出：3
解释：第 5 小的数字是 3 。

示例 2：

输入：m = 2, n = 3, k = 6
输出：6
解释：第 6 小的数字是 6 。

提示：

1 <= m, n <= 3 * 10⁴
1 <= k <= m * n

lightbulb

解题思路

方法一：二分查找

题目可以转换为，求有多少个数不超过 x。对于每一行 i，所有数都是 i 的倍数，不超过 x 的个数有 x / i 个。

二分枚举 x，累加每一行不超过 x 的个数，得到 cnt。找到 cnt >= k 的最小 x。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        left, right = 1, m * n
        while left < right:
            mid = (left + right) >> 1
            cnt = 0
            for i in range(1, m + 1):
                cnt += min(mid // i, n)
            if cnt >= k:
                right = mid
            else:
                left = mid + 1
        return left

speed

复杂度分析

指标	值
时间	O(m * \log (m*n))
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
The candidate should focus on utilizing binary search over the answer space effectively.
question_mark
Expect the candidate to leverage the properties of the multiplication table to count elements efficiently in each row.
question_mark
Look for an understanding of how to minimize unnecessary calculations through early termination or efficient counting.

warning

常见陷阱

外企场景

error
A common mistake is performing a brute force search, where the candidate tries to generate the entire multiplication table to find the kth smallest number. This approach is inefficient and fails for large inputs.
error
Misunderstanding how to count elements less than or equal to a mid value in each row of the multiplication table can lead to incorrect results or inefficient solutions.
error
Candidates may miss the optimal space complexity, leading to an unnecessarily large space usage.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the multiplication table is much larger? How would the solution scale with larger m and n?
arrow_right_alt
Can the problem be solved without using binary search? If so, what trade-offs would be involved?
arrow_right_alt
How can this approach be applied if the table is not sorted or if the rows and columns are not strictly increasing?

help

常见问题

外企场景

继续练习

#633 平方数之和 #710 黑名单中的随机数 #754 到达终点数字