题目要求

在这里插入图片描述

思路：二分

每行每列都是单调递增的；
统计每行（列）中小于 $m i d$ 的数记les，等于 $m i d$ 的数记equ，设当前行号为 $i$ （行列等价，此处用行做基准论述）：
- 当前行（列）最大值为 $i\times m$ ；
- 若 $i\times m<mid$ ，也就是整行都小于 $m i d$ ，此时 $l e s$ 数量加 $m$ ；
- 若 $i\times m>= mid$ ，判断是否有于 $m i d$ 相等的数分情况处理。
然后根据 $k$ 和 $c n t$ 的关系移动左右指针。
实现中简化判断，直接取 $m i d / i$ 和当前行元素个数中较小的一个。

Java

class Solution {
    public int findKthNumber(int m, int n, int k) {
        int mi = Math.min(m, n), ma = Math.max(m, n);
        int l = 1, r = m * n;
        while(l < r) {
            int mid = l + r >> 1, cnt = 0;
            for(int i = 1; i <= mi; i++)
                cnt += Math.min(mid / i, ma);
            if(cnt >= k)
                r = mid;
            else
                l = mid + 1;
        }
        return r;
    }
}

时间复杂度： $O(\min(n,m) \times \log mn)$
空间复杂度： $O (1)$

C++

class Solution {
public:
    int findKthNumber(int m, int n, int k) {
        int mi = min(m, n), ma = max(m, n);
        int l = 1, r = m * n;
        while(l < r) {
            int mid = l + r >> 1, cnt = 0;
            for(int i = 1; i <= mi; i++)
                cnt += min(mid / i, ma);
            if(cnt >= k)
                r = mid;
            else
                l = mid + 1;
        }
        return r;
    }
};

时间复杂度： $O(\min(n,m) \times \log mn)$
空间复杂度： $O (1)$

Rust

impl Solution {
    pub fn find_kth_number(m: i32, n: i32, k: i32) -> i32 {
        let(mut l, mut r) = (1, m * n + 1);
        while l < r {
            let(mid, mut cnt) = (l + ((r - l) >> 1), 0);
            for i in 1..=m {
                cnt += n.min(mid / i);
            }
            if cnt >= k {
                r = mid;
            }
            else{
                l = mid + 1;
            } 
        }
        r
    }
}