例 1：
输入: m = 3, n = 3, k = 5
输出: 3
解释:
乘法表:
1 2 3
2 4 6
3 6 9
第5小的数字是 3 (1, 2, 2, 3, 3).
例 2：
输入: m = 2, n = 3, k = 6
输出: 6
解释:
乘法表:
1 2 3
2 4 6
第6小的数字是 6 (1, 2, 2, 3, 4, 6).
思路
题目中的乘法表不论是从左到右还是从上到下，都是严格的单调递增，我们很容易想到二分查找。
当我们求第k小时，可以通过求x是第几小，来不断的接近k，使得x == k。
由于第i行都是第一行的i倍，所以第i行小于等于x的个数为min(x / i , n),因为第i行最多只有n个数
C++代码：
class Solution {
public:
int findKthNumber(int m, int n, int k) {
if (m > n) return findKthNumber(n, m, k);
int left = 1, right = n * m; // 最大 9e8
while (left < right) {
int mid = left + (right - left) / 2;
if (check(m, n, k, mid)) left = mid + 1;
else right = mid;
}
return left;
}
bool check(int m, int n, int k, int x) {
int cnt = 0;
for (int i = 1; i <= m; ++i) cnt += min(n, x / i);
return cnt < k;
}
};
