Java实现 LeetCode 668 乘法表中第k小的数（二分）

冷不防 2023-07-21 13:27 8阅读 0赞

## 668. 乘法表中第k小的数 ##

几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第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\] 之间。

class Solution { 
       public int findKthNumber(int m, int n, int k) { 
           int left = 1, right = m*n;
            while(left < right){ 
                int mid = left + (right-left)/2;
                if(counter(m, n, mid) >= k){ 
                    right = mid;
                }else{ 
                    left = mid + 1;
                }
            }
            return left;
        }
        public int counter(int m, int n, int mid) { 
            int x = m;
            int y = 1;
            int counter = 0;
            while (x >= 1 && y <= n) { 
                if (x * y <= mid) { 
                    counter += x;
                    y++;
                } else { 
                    x--;
                }
            }
            return counter;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，8人围观）

还没有评论，来说两句吧...

相关阅读

相关 7-1 寻找第k小的数 (20 分)

7-1 寻找第k小的数 (20 分) 给定若干整数，请设计一个高效的算法，确定第k小的数。输入格式: 测试数据有多组，处理到文件尾。每组测试数据的第1行输入2个整数

深藏阁楼爱情的钟/ 2023年10月11日 16:49/ 0 赞/ 16 阅读

相关 Java实现 LeetCode 668 乘法表中第k小的数（二分）

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

冷不防/ 2023年07月21日 13:27/ 0 赞/ 9 阅读

相关 LeetCode 二叉搜索树中第k小的数

中序遍历 + 一个计数变量即可解决 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0c

向右看齐/ 2023年07月14日 08:22/ 0 赞/ 6 阅读

相关找出数组中的第K大的数或者第K小的数

class Solution { public: int findKthLargest(vector<int>& res, int k)

本是古典何须时尚/ 2022年12月31日 01:25/ 0 赞/ 183 阅读

相关 Leetcode 668. 乘法表中第k小的数（DAY 190）---- 二分查找学习期

文章目录原题题目代码实现（首刷超时 TLE 优先队列 59/70）代码实现（首刷看了思路二分优化） ---------

Myth丶恋晨/ 2022年09月16日 04:46/ 0 赞/ 145 阅读

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

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

短命女/ 2022年09月02日 11:34/ 0 赞/ 147 阅读

相关求前K小的数和第K小的数

求前K小的数和第K小的数 1. 前K小的数（堆排序实现） include<iostream> include<algorithm> inclu

落日映苍穹つ/ 2022年08月06日 13:19/ 0 赞/ 184 阅读

相关 LeetCode230. 二叉搜索树中第K小的元素

给定一个二叉搜索树，编写一个函数 `kthSmallest` 来查找其中第 k 个最小的元素。说明：你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

╰半夏微凉°/ 2022年05月06日 04:26/ 0 赞/ 156 阅读

相关 leetcode 二叉搜索树中第K小的元素

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。说明：你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。示

朴灿烈づ我的快乐病毒、/ 2022年03月18日 02:44/ 0 赞/ 137 阅读

相关 LeetCode230.二叉搜索树中第K小的元素

参考链接：[https://blog.csdn.net/yuanliang861/article/details/84640069][https_blog.csdn.net_y

青旅半醒/ 2022年02月15日 08:51/ 0 赞/ 177 阅读