668.Kth Smallest Number in Multiplication Table¶
Tags: Hard
Binary Search
Links: https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/
Nearly every one have used the Multiplication Table. But could you find out the k-th
smallest number quickly from the multiplication table?
Given the height m
and the length n
of a m * n
Multiplication Table, and a positive integer k
, you need to return the k-th
smallest number in this table.
Example 1:
Input: m = 3, n = 3, k = 5
Output:
Explanation:
The Multiplication Table:
1 2 3
2 4 6
3 6 9
The 5-th smallest number is 3 (1, 2, 2, 3, 3).
Example 2:
Input: m = 2, n = 3, k = 6
Output:
Explanation:
The Multiplication Table:
1 2 3
2 4 6
The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6).
Note:
- The
m
andn
will be in the range [1, 30000]. - The
k
will be in the range [1, m * n]
class Solution {
public:
int findKthNumber(int m, int n, int k) {
int left = 1, right = m * n;
while (left < right) {
int mid = left + (right - left) / 2, cnt = 0;
for (int i = 1; i <= m; ++i) {
cnt += (mid > n * i) ? n : (mid / i);
}
if (cnt < k) left = mid + 1;
else right = mid;
}
return right;
}
};
解法二:
不是逐行来统计,而是从左下角的数字开始统计,如果该数字小于mid,说明该数字及上方所有数字都小于mid,cnt加上i个,然后向右移动一位继续比较。如果当前数字小于mid了,那么向上移动一位,直到横纵方向有一个越界停止,其他部分都和上面的解法相同,
class Solution {
public:
int findKthNumber(int m, int n, int k) {
int left = 1, right = m * n;
while (left < right) {
int mid = left + (right - left) / 2, cnt = 0, i = m, j = 1;
while (i >= 1 && j <= n) {
if (i * j <= mid) {
cnt += i;
++j;
} else {
--i;
}
}
if (cnt < k) left = mid + 1;
else right = mid;
}
return right;
}
};
对解法二的优化,再快一点,使用除法来快速定位新的j值,然后迅速算出当前行的小于mid的数的个数,然后快速更新i的值,这比之前那种一次只加1或减1的方法要高效许多.
class Solution {
public:
int findKthNumber(int m, int n, int k) {
int left = 1, right = m * n;
while (left < right) {
int mid = left + (right - left) / 2, cnt = 0, i = m, j = 1;
while (i >= 1 && j <= n) {
int t = j;
j = (mid > n * i) ? n + 1 : (mid / i + 1);
cnt += (j - t) * i;
i = mid / j;
}
if (cnt < k) left = mid + 1;
else right = mid;
}
return right;
}
};