kth-smallest-number-in-multiplication-table

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Nearly everyone has used the <a href="https://en.wikipedia.org/wiki/Multiplication_table" target="_blank">Multiplication Table</a>. The multiplication table of size <code>m x n</code> is an integer matrix <code>mat</code> where <code>mat[i][j] == i * j</code> (1-indexed).

Given three integers <code>m</code>, <code>n</code>, and <code>k</code>, return the <code>kth</code> smallest element in the <code>m x n</code> multiplication table.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/02/multtable1-grid.jpg" style="width: 500px; height: 254px;" />
<pre>
Input: m = 3, n = 3, k = 5
Output: 3
Explanation: The 5th smallest number is 3.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/02/multtable2-grid.jpg" style="width: 493px; height: 293px;" />
<pre>
Input: m = 2, n = 3, k = 6
Output: 6
Explanation: The 6th smallest number is 6.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= m, n &lt;= 3 * 104</code></li>
	<li><code>1 &lt;= k &lt;= m * n</code></li>
</ul>

findKthNumber

Kth Smallest Number in Multiplication Table

Kth Smallest Element in a Sorted Matrix

kth-smallest-element-in-a-sorted-matrix

有序矩阵中第 K 小的元素

Find K-th Smallest Pair Distance

find-k-th-smallest-pair-distance

找出第 K 小的数对距离

K-th Smallest Prime Fraction

k-th-smallest-prime-fraction

第 K 个最小的质数分数

Minimum Time to Eat All Grains

minimum-time-to-eat-all-grains

吃掉所有谷子的最短时间

Kth Smallest Amount With Single Denomination Combination

kth-smallest-amount-with-single-denomination-combination

单面值组合的第 K 小金额

Math

Binary Search

几乎每一个人都用&nbsp;<a href="https://baike.baidu.com/item/%E4%B9%98%E6%B3%95%E8%A1%A8">乘法表</a>。但是你能在乘法表中快速找到第 <code>k</code> 小的数字吗？

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

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

<div class="original__bRMd">
<div>
&nbsp;

示例 1：
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/02/multtable1-grid.jpg" style="width: 500px; height: 254px;" />
<pre>
输入：m = 3, n = 3, k = 5
输出：3
解释：第 5 小的数字是 3 。
</pre>

示例 2：
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/02/multtable2-grid.jpg" style="width: 493px; height: 293px;" />
<pre>
输入：m = 2, n = 3, k = 6
输出：6
解释：第 6 小的数字是 6 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= m, n &lt;= 3 * 104</code></li>
	<li><code>1 &lt;= k &lt;= m * n</code></li>
</ul>
</div>
</div>