『LeetCode』668 乘法表中第k小的数

题目

668. 乘法表中第k小的数

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

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

例 1：

输入: m = 3, n = 3, k = 5
输出: 3
解释:乘法表:
123
246
369

第5小的数字是 3 (1, 2, 2, 3, 3).

例 2：

输入: m = 2, n = 3, k = 6
输出: 6
解释:乘法表:
123
246

第6小的数字是 6 (1, 2, 2, 3, 4, 6).

注意：

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

相似题目

题解

【乘法表中第k小的数】二分查找

二分查找

不难发现其实乘法表是一个有序的矩阵，其有序性体现在，同一行中左边的小于右边的，同一列中上面的小于下面的，根据这一点，可能很快就会想到矩阵中二分查找(有序矩阵中第 K 小的元素 (中等))，但由于乘法表中有很多重复元素，导致无法使用矩阵二分查找的方法直接在矩阵中查找, 而是需要换个思路，给出一个元素 \(x\), 可以很容易计算具体在矩阵中的大小次序（即第 \(k\) 大的元素, \(k\) 的值具体是多少）。

实际上这是一个使用二分法猜答案的过程，二分的猜一个答案然后验证猜得对不对，然后验证。

# Code language: Python
class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        if m > n:
            return self.findKthNumber(n, m, k)
        left, right = 1, n * m
        def check(x):
            return sum(min(n, x // row) for row in range(1, m + 1))
        while left < right:
            mid = (left + right) >> 1
            if check(mid) < k:
                left = mid + 1
            else:
                right = mid
        return left

// Code language: Java
class Solution {
    public int findKthNumber(int m, int n, int k) {
        if (m > n) return findKthNumber(n, m, k);
        int left = 1, right = n * m; // 最大 9e8
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (check(m, n, k, mid)) left = mid + 1;
            else right = mid;
        }
        return left;
    }

    public boolean check(int m, int n, int k, int x) {
        int cnt = 0;
        for (int i = 1; i <= m; ++i) cnt += Math.min(n, x / i);
        return cnt < k;
    }
}

// Code language: Cpp
class Solution {
public:
    int findKthNumber(int m, int n, int k) {
        if (m > n) return findKthNumber(n, m, k);
        int left = 1, right = n * m; // 最大 9e8
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (check(m, n, k, mid)) left = mid + 1;
            else right = mid;
        }
        return left;
    }

    bool check(int m, int n, int k, int x) {
        int cnt = 0;
        for (int i = 1; i <= m; ++i) cnt += min(n, x / i);
        return cnt < k;
    }
};

// Code language: C
bool check(int m, int n, int k, int x) {
    int cnt = 0;
    for (int i = 1; i <= m; ++i) cnt += n < x / i ? n : x / i;
    return cnt < k;
}

int findKthNumber(int m, int n, int k){
    if (m > n) return findKthNumber(n, m, k);
    int left = 1, right = n * m; // 最大 9e8
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (check(m, n, k, mid)) left = mid + 1;
        else right = mid;
    }
    return left;
}

时间复杂度: \(O(min(n, m) \log \max(n, m) \log nm)\)
空间复杂度: \(O(1)\)