668. Kth Smallest Number in Multiplication Table

https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/description/

找m*n乘法表中第K小的。固定范围找第K大/小用二分值范围。二分的范围为给定乘法表取值范围[1, m * n]。每次对候选mid找乘法表中小于mid的个数，如果比K小说明mid还可以往前走。乘法表是:

1 2 3 ... n

2*1 2 * 2 2 * 3 ... 2 * n

...

m * 1 m * 2 .... m * n

因此可以遍历1...m看mid / i 能到哪。

/*
 * @lc app=leetcode id=668 lang=cpp
 *
 * [668] Kth Smallest Number in Multiplication Table
 *
 * https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/description/
 *
 * algorithms
 * Hard (42.78%)
 * Likes:    387
 * Dislikes: 19
 * Total Accepted:    14.8K
 * Total Submissions: 34.4K
 * Testcase Example:  '3\n3\n5'
 *
 * 
 * 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 and n will be in the range [1, 30000].
 * The k will be in the range [1, m * n]
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    int findKthNumber(int m, int n, int k) {
        const auto LEX = [&](int x) {
            int count = 0;
            for (int i = 1; i <= m; ++i) {
                count += min(n, x / i);
            }
            return count;
        }; 
        int start = 1, end = m * n;
        while (start < end) {
            int mid = start + (end - mid) / 2;
            if (LEX(mid) < k) start = mid + 1;
            else end = mid;
        }
        return start;
    }
};
// @lc code=end