📍前言

🕺作者： 迷茫的启明星

学习路线

C语言从0到1

C++初阶

数据结构从0到1

😘欢迎关注：👍点赞🙌收藏✍️留言

🏇码字不易，你的👍点赞🙌收藏❤️关注对我真的很重要，有问题可在评论区提出，感谢阅读！！！

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

在另一篇博客里讲过二分法的模板：

《二分法的模板讲解》

问题描述

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

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

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

解题思路

fun函数：

这个函数接收三个参数：m，n和num。m和n分别表示乘法表的行数和列数，num表示需要比较的值。这个函数通过遍历乘法表的每一行，计算在当前行中，有多少个值小于等于num。min(num/i, n)表达式用于计算在当前行中有多少个值小于等于num。

我们通过一个具体的例子来理解。

假设乘法表的行数 m 为 3，列数 n 为 4，我们要计算不超过给定值 num 的值的数量。

首先，我们需要遍历乘法表的每一行。在第一行（i=1）中，不超过 num 的值的最大个数为 num / i = num / 1 = num，因为第一行的每个元素都小于等于 num。

接下来，在第二行（i=2）中，不超过 num 的值的最大个数为 num / i = num / 2。但是我们还需要考虑乘法表的列数 n。假设 num / 2 > n，也就是说当前行满足条件的数量超过了列数。那么实际满足条件的数量应取 n。如果 num / 2 <= n，那么实际满足条件的数量就是 num / 2。

继续进行到第三行（i=3），同样计算不超过 num 的值的最大个数为 num / i = num / 3。然后再根据列数 n 进行判断。

例如，假设 num 为 6，乘法表为：

1 2 3 4
2 4 6 8 
3 6 9 12

我们来计算不超过 num = 6 的值的数量。

在第一行中， num / i = 6 / 1 = 6，因此整个第一行都满足条件。所以累加数量 count = 4（此处 n=4）。

在第二行中， num / i = 6 / 2 = 3，由于 num / i > n，所以实际满足条件的数量只有 n = 4。所以累加数量 count = 4 + 4 = 8。

在第三行中， num / i = 6 / 3 = 2，同样由于 num / i <= n，所以实际满足条件的数量为 num / i = 2。所以累加数量 count = 8 + 2 = 10。

最终，累加的数量为 10，即不超过 num = 6 的值的数量。

findKthNumber函数：

这个函数接收三个参数：m，n和k。m和n分别表示乘法表的行数和列数，k表示需要查找的目标值在乘法表中的排名。

这个函数首先初始化一个左界left为1，一个右界right为m*n，以及一个中间值mid。然后，使用二分查找法来缩小范围。在每次循环中，计算fun函数在当前mid值下的结果，并将其与目标值k进行比较。如果temp < k，说明当前mid值在目标值的左边（比目标值小），所以可以缩小左边界；否则，缩小右边界。

在二分查找过程中，如果temp等于k，不能立即返回结果，因为当前的mid值可能不在乘法表中。所以需要继续缩小范围，直到left = right。最终返回的left值就是第k小的数。

总结一下，这个代码的主要思路是通过二分查找法在有序的乘法表中查找第k小的数。在查找过程中，fun函数用于计算在当前mid值下的结果，然后根据结果调整查找范围。

代码实现

下面是使用C++实现的查找乘法表中第K小数的算法：

class Solution {
public:
    //Binary Search for value
    //跟普通二分不一样 普通二分把下标来当作边界，而这里的二分则是把值来当作边界
    int fun(int m, int n, int num) {//函数功能：获得在m*n的乘法表中，找出有多少个值 <= num。返回满足条件的值的数量
        int count = 0;
        for(int i = 1; i<=m; ++i) {//行从第一行开始
            count += min(num/i, n);//此表达式的含义：num这个值在当前第i行，有多少个值不比它大（<=num的个数）
        }
        return count;
    }
    int findKthNumber(int m, int n, int k) {
        if(k == 1) return 1;
        if(k == m*n) return m*n;
        int left = 1, right = m*n, mid;//值来当作边界，乘法表（m*n）最小是1，最大是m*n
        while(left < right) {
            mid = (left+right) >> 1;
            int temp = fun(m, n, mid);//得到在乘法表中 值 <= mid 的数量
            if(temp < k) {
                left = mid+1;//如果temp < k, 说明当前mid这个值在目标值的左边（比目标值小），所以可以缩小边界
            }
            else right = mid;
          /*temp >= k， 在temp>k时，为什么不取 right = mid-1，而是right = mid。
          因为我们的目标值可能存在重复，比如 123334，如果我选择要找第3小的数，
          而mid当前恰好=3，那么temp得到的结果会是5（<=mid）。如果我们选择right = mid-1=2。           那么将会运行错误导致结果错误。在temp = k时，为什么不能立马返回结果呢，
          而是继续运行缩小边界？因为我们当前的mid可能是一个不在乘法表中的值，
          毕竟mid=(left+right) >> 1; 所以立即返回可能返回错误答案。
          所以一定收缩范围 直到left=right。最终返回的一定是正确值
          （若答案t的temp = k， 而某一非表值x的temp也=k， 那么t一定比x小，
          最终x也会被right缩小导致出局）。*/
        }
        return left;
    }
};

总结

本文介绍了一种基于二分查找的算法，用于在给定的乘法表中搜索第K小的数。该算法通过每次迭代将搜索区间缩小一半来逐步逼近目标值。我们首先计算乘法表的最小值和最大值，然后使用二分查找算法在乘法表中查找第K小的数。

在每次迭代中，我们计算中间值mid，并使用辅助函数fun计算在乘法表中有多少个值不超过mid。根据fun的返回值与k的比较结果，我们将搜索区间缩小到左侧或右侧。当left等于right时，算法终止，返回left作为第K小的数。

使用C++实现的查找乘法表中第K小数的算法代码简洁易懂，易于理解和修改。在给定乘法表的情况下，该算法可以快速找到第K小的数，具有较高的实用性和效率。

本文由mdnice多平台发布