1.题目基本信息

1.1.题目描述

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

乘法表是大小为 m x n 的一个整数矩阵，其中 mat[i][j] == i * j（下标从 1 开始）。

给你三个整数 m、n 和 k，请你在大小为 m x n 的乘法表中，找出并返回第 k 小的数字。

1.2.题目地址

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

2.解题方法

2.1.解题思路

二分查找

2.2.解题步骤

第一步，构建函数。实现获取乘法表中小于等于x的元素的个数

第二步，红蓝染色定义。红色指向被乘法表中小于k个元素小于等于的x，蓝色指向被乘法表中大于等于k个元素小于等于的x；维护left-1始终指向红色区域，right+1始终指向蓝色区域；最终的left或者right+1即为题解

3.解题代码

python代码

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        # 思路：二分查找
        # 第一步，构建函数。实现获取乘法表中小于等于x的元素的个数
        def getCnt(x:int) -> int:
            ans = 0
            for i in range(m):
                a = x // (i + 1)
                if a > 0:
                    ans += min(a, n)
                else:
                    break
            return ans
        # 第二步，红蓝染色定义。红色指向`被乘法表中小于k个元素`小于等于的x，蓝色指向`被乘法表中大于等于k个元素`小于等于的x；维护left-1始终指向红色区域，right+1始终指向蓝色区域；最终的left或者right+1即为题解
        left, right = 1, m * n
        while left <= right:
            mid = left + (right - left) // 2
            if getCnt(mid) < k:
                left = mid + 1
            else:
                right = mid - 1
        # return right + 1
        return left

c++代码

class Solution {
public:
    int getCnt (int x, int m, int n) {
        int ans = 0;
        for (int i = 0; i < m; i++) {
            int a = x / (i + 1);
            if (a > 0) {
                ans += min(a, n);
            } else {
                break;
            }
        }
        return ans;
    }

    int findKthNumber(int m, int n, int k) {
        int left = 1, right = m * n;
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (getCnt(mid, m, n) < k) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

4.执行结果