题目：https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/description/
668. 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
mandnwill be in the range [1, 30000]. - The
kwill be in the range [1, m * n]
二分答案，用lower_bound和upper_bound的思想。
这居然是一道hard题，难以置信，就这个难度啊。
我被自己蠢哭了，把它当成ACM题，以为时间只有一秒，非要优化到O(n*log(n))。
没想到时间和空间复杂度O（n*m）就可以过了。
不说了，第一次过hard题，20分钟，直接上代码把：
class Solution {
public:
int findKthNumber(int m, int n, int k) {
if(m > n) swap(m, n);
int l = ; int r = m*n;
while(l < r){
int mid = (l+r)/;
int p = judge(m, n, k, mid);
// cout << p << " ";
if(p == ){
return mid;
}else if(p == ){
r = mid-;
}else if(p == ){
l = mid+;
}
}
return r;
}
int judge(int m, int n, int k, int mid){
int sum1 = , sum2 = ;
for(int i = ;i <= m; i++){
if(i * n <= mid){
sum2 += n;
}else{
sum2 += mid/i;
}
if(i * n < mid){
sum1 += n;
}else{
sum1 += (mid-)/i;
}
// cout << sum1 << endl;
}
cout << mid << " " << sum1 << " " << sum2 << endl;
if(sum1 < k && sum2 >= k){
return ;
}else if(sum1 >= k){
return ;
}else if(sum2 < k){
return ;
}
}
};