0668. Kth Smallest Number in Multiplication Table

题目信息

题号:

0668

难度:

Hard

主题:

乘法表、排序名次、重复值、一基第 k 小

原题:

LeetCode 0668

重点:

表中第 i 行第 j 列为 i*j、同一数值在不同格子出现时重复占据名次、k 从 1 开始

题目重述

构造一个 m × n 的乘法表,其中行号和列号都从 1 开始,格子 (i, j) 的值为 i * j。把全部 m*n 个格子值按非递减顺序排列,返回其中第 k 小的数。

相同数值若来自不同格子,需要按出现次数重复计入排序序列。m、n 位于 [1, 3 * 10^4],k 位于 [1, m*n],名次采用一基编号。

自建示例

重复值占据多个名次:

输入:m = 2,n = 4,k = 5
输出:4
解释:表中数值排序后为 [1,2,2,3,4,4,6,8],第五个数是 4。

只有一行:

输入:m = 1,n = 5,k = 4
输出:4
解释:乘法表就是 [1,2,3,4,5],第四小的数为 4。