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

文章目次

• 
  
  
  
  • 1. 题目
    
  • 2. 解题
    
  
  

1. 题目

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

1. 例 1：输入: m = 3, n = 3, k = 5输出: 3表明: 乘法表:1        2        32        4        63        6        9第5小的数字是 3 (1, 2, 2, 3, 3).例 2：输入: m = 2, n = 3, k = 6输出: 6表明: 乘法表:1        2        32        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. 解题

雷同题目参考：LeetCode 1231. 分享巧克力（极小极大化 二分查找）
<ul>m*n 的范围靠近 10^9 ，O(mn) 以上时间复杂度的算法都会超时
思量二分查找，L = 1, R = m*n, 选取mid，查抄 1);            if(ok(m,n,mid,k))            {   //选取数字为mid时，有 >= k 个数