请选择 进入手机版 | 继续访问电脑版

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

[复制链接]
唐少琼 发表于 2021-1-3 12:23:32 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
文章目次



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 个数
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )