LeetCode 668 乘法表中第k小的数[二分法] HERODING的LeetCode之路

解题思路：
这道题在注意部分就明确表明了不能通过构建乘法表的方法进行统计，因为m * n的结果可能很大，直接内存爆炸。首先观察规律，对于任何一个数num，它在第i行中大于(num/i, n)个数，num/i 为如果该数在i行所处的位置，通过二分法，不断查找不大于mid的数的个数，直到left和right相遇，返回left，代码如下：

class Solution {
public:
    int findKthNumber(int m, int n, int k) {
        int left = 0, right = m * n;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(count(m, n, mid) < k) {
                left = mid + 1;
            } else right = mid;
        }
        return left;
    }

    // 统计不大于mid的个数
    int count(int m, int n, int mid) {
        int res = 0;
        for(int i = 1; i <= m; i ++) {
             res += min(mid / i ,n);
        }
        return res;
    }
};

简单优化一下如下：

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) >> 1);
            if(count(m, n, mid) < k) {
                left = mid + 1;
            } else right = mid;
        }
        return left;
    }

    // 统计不大于mid的个数
    int count(int m, int n, int mid) {
        // 所有数都小的行数
        int res = mid / n * n;
        for(int i = 1 + mid / n; i <= min(mid, m); i ++) {
             res += min(mid / i ,n);
        }
        return res;
    }
};