golang 解法, 执行用时: 12 ms, 内存消耗: 1.9 MB, 提交时间: 2023-04-11 19:41:39

func findKthNumber(m, n, k int) int {
    return sort.Search(m*n, func(x int) bool {
        count := x / n * n
        for i := x / n + 1; i <= m; i++ {
            count += x / i
        }
        return count >= k
    })
}

python3 解法, 执行用时: 916 ms, 内存消耗: 14.8 MB, 提交时间: 2023-04-11 19:41:12

class Solution:
    def cnt(self, mid: int, m: int, n: int) -> int:
        ret, i, j = 0, m, 1
        while(i >= 1 and j <= n):
            if i*j <= mid:
                ret += i
                j += 1
            else:
                i -= 1
        return ret

    def findKthNumber(self, m: int, n: int, k: int) -> int:
        l, r = 1, m*n
        while(l < r):
            mid = (l+r) >> 1
            if(self.cnt(mid, m, n) < k):
                l = mid+1
            else:
                r = mid
        return l

golang 解法, 执行用时: 16 ms, 内存消耗: 1.8 MB, 提交时间: 2023-04-11 19:40:20

func findKthNumber(m int, n int, k int) int {
    if m > n {
        m, n = n, m
    }
    left, right := 0, m * n
    check := func(x int) (sum int) {
        for i := 1; i <= m; i++ {
            if cur := x / i; cur <= n {
                sum += cur
            } else {
                sum += n
            }
        }
        return
    }
    for left < right {
        mid := (left + right) >> 1
        if check(mid) >= k {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

javascript 解法, 执行用时: 80 ms, 内存消耗: 40.6 MB, 提交时间: 2023-04-11 19:40:06

/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var findKthNumber = function(m, n, k) {
    if (m > n) {
        [m, n] = [n, m]
    }
    let left = 0, right = m * n
    const check = (x) => {
        let sum = 0
        for(let i = 1; i<= m; i++) {
            sum += Math.min(n, Math.floor(x / i))
        }
        return sum
    }
    while(left < right) {
        const mid = (left + right) >> 1
        if (check(mid) >= k) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
};

java 解法, 执行用时: 7 ms, 内存消耗: 38.3 MB, 提交时间: 2023-04-11 19:39:53

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

    private int count(int m, int n, int x) {
        int sum = 0;
        for(int i = 1; i <= m; i++) {
            sum += Math.min(n, x / i);
        }
        return sum;
    }
}

python3 解法, 执行用时: 532 ms, 内存消耗: 15 MB, 提交时间: 2023-04-11 19:39:33

'''
乘法表中第k小的数并不能直观地得到, 但是乘法表中的某个数x，比它小的数有多少个是很好统计的(每行i都是x/i个)。
对乘法表的值域做比它小的个数的二分，找到k对应的位置。

有朋友可能问了，这个值域中还包括并不在乘法表中的质数呢？
根据二段性，比这个质数小一点的乘法表中的数和这个质数，在这个乘法表中小于它的个数是一样的，
我们会取左边界也就是乘法表里的数(这也是为啥Py里用bisect_left而不是bisect_right)。

PS:
小优化，交换行数，对小的行数统计二分值
'''
class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        return bisect_left(range(m * n + 1), k, key=lambda x:sum(min(n, x // i) for i in range(1, m + 1))) if n >= m else self.findKthNumber(n, m, k)