0668. Kth Smallest Number in Multiplication Table¶
题目信息¶
- 题号:
0668
- 难度:
Hard
- 主题:
乘法表、排序名次、重复值、一基第 k 小
- 原题:
- 重点:
表中第 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。