Appearance
668. 乘法表中第k小的数
题目描述
几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第 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 * 104
- `1 <= k <= m * n`
难度： Hard
题解代码
javascript
/**
* @param {number} m
* @param {number} n
* @param {number} k
* @return {number}
*/
// 二分法
var findKthNumber = function(m, n, k) {
let left = 1
let right = m*n
while(left < right) {
const mid = (left+right) >> 1;
if(count(m, n, mid) >= k) {
right = mid
} else {
left = mid+1;
}
}
return left;
};
// 统计乘法表中有多少个小于等于 k 的数目
function count(m, n, num){
let count = 0;
for(let i = 1; i <= m; ++i) {
count += Math.min(parseInt(num / i), n);
}
return count
}
// 用优先队列 用例通过84%, 超时了。
// var findKthNumber = function (m, n, k) {
// const pq = new MinPriorityQueue({
// compare: (a, b) => (a[0] + 1) * (a[1] + 1) - (b[0] + 1) * (b[1] + 1)
// });
// for (let i = 0; i < m; i++) {
// pq.enqueue([i, 0])
// }
// while (k-- >= 0 && pq.size()) {
// const [i, j] = pq.dequeue();
// if (!k) return (i + 1) * (j + 1)
// if (j + 1 < n) pq.enqueue([i, j + 1]);
// }
// }