668 乘法表中第k小的数（二分查找）

短命女 2022-09-02 11:34 114阅读 0赞

**1. 问题描述：**

几乎每一个人都用乘法表。但是你能在乘法表中快速找到第k小的数字吗？给定高度m 、宽度n 的一张 m \* n的乘法表，以及正整数k，你需要返回表中第k小的数字。

**例 1：**

输入: m = 3, n = 3, k = 5  
输出: 3  
解释:  
乘法表:  
1 2 3  
2 4 6  
3 6 9  
第5小的数字是 3 (1, 2, 2, 3, 3).

**例 2：**

输入: m = 2, n = 3, k = 6  
输出: 6  
解释:  
乘法表:  
1 2 3  
2 4 6  
第6小的数字是 6 (1, 2, 2, 3, 4, 6).  
注意：  
m 和 n 的范围在 \[1, 30000\] 之间。  
k 的范围在 \[1, m \* n\] 之间。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/kth-smallest-number-in-multiplication-table

**2. 思路分析：**

分析题目可以知道我们需要找到小于等于k的第一个数字，根据这个特点可以知道我们可以使用**二分**来解决（小于等于，大于等于...的第一个元素是可以使用二分查找的一类问题），我们可以将乘法表看成是一个有序的数组，我们需要在这个有序的数组中找到小于等于k的第一个元素，所以问题的核心是如何判断当前的中点mid是否满足题目的要求，也即判断出当前乘法表中有多少个数是小于等于mid的，我们其实可以计算每一行有多少个数小于等于mid然后累加起来即可，以每一行的第一个数字计算即可，i \* x <= mid也即x <= mid / i，其中i为每行第一个数字，并且每一行最多有n个数字，所以两者取一个min即可。在二分的时候发现当前的mid是大于等于k的说明答案在左边，否则答案是在右边的。

**3. 代码如下：**

class Solution:
        def check(self, m: int, n: int, mid: int):
            res = 0
            # 计算每行有多少个数字小于等于mid, 以每行第一个数字进行计算即可
            for i in range(1, m + 1):
                res += min(n, mid // i)
            return res
    
        # 二分查找
        def findKthNumber(self, m: int, n: int, k: int) -> int:
            l, r = 1, m * n
            while l < r:
                mid = l + r >> 1
                # 说明答案在左边
                if self.check(m, n, mid) >= k:
                    r = mid
                # 说明答案在右边
                else:
                    l = mid + 1
            return r