几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第k小的数字吗？

    给定高度m 、宽度n 的一张 m * n的乘法表，以及正整数k，你需要返回表中第k 小的数字。

    例 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).
    注意：

    m 和 n 的范围在 [1, 30000] 之间。
    k 的范围在 [1, m * n] 之间。

    1. class Solution {
    2.     /**
    3.     乘法表行列上的数都是单调递增的，可用二分来枚举小于等于当前数的数量
    4.     i * m < mid 整行都是小于mid i * m >= mid 分mid能不能整除i来判断是不是在当前行
    5.      */
    6.     int n, m, k;
    7.     public int findKthNumber(int _m, int _n, int _k) {
    8.         //乘法表是对称的，选择小的来枚举
    9.         n = Math.min(_n, _m); m = Math.max(_n , _m); k = _k;
    10.         int l = 1, r = m * n;
    11.         while (l < r) {
    12.             int mid = l + r >> 1;
    13.             if (check(mid)) r = mid;
    14.             else l = mid + 1;
    15.         }
    16.         return l;
    17.     }
    19.     boolean check(int mid) {
    20.         int cnt = 0;
    21.         for (int i = 1; i <= n; ++i) {
    22.             if (i * m < mid) cnt += m;
    23.             else cnt += mid / i;
    24.         }
    25.         return cnt >= k;
    26.     }
    27. }