LeetCode hard 668. Kth Smallest Number in Multiplication Table（二分答案，一次过了，好开心，哈哈哈哈）
2024-08-23 07:19:47
题目：https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/description/
668. Kth Smallest Number in Multiplication Table
Nearly every one have used the Multiplication Table. But could you find out the k-th smallest number quickly from the multiplication table?
Given the height m and the length n of a m * n Multiplication Table, and a positive integer k, you need to return the k-th smallest number in this table.
Example 1:
Input: m = 3, n = 3, k = 5
Output:
Explanation:
The Multiplication Table:
1 2 3
2 4 6
3 6 9 The 5-th smallest number is 3 (1, 2, 2, 3, 3).
Example 2:
Input: m = 2, n = 3, k = 6
Output:
Explanation:
The Multiplication Table:
1 2 3
2 4 6 The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6).
Note:
- The
mandnwill be in the range [1, 30000]. - The
kwill be in the range [1, m * n]
二分答案，用lower_bound和upper_bound的思想。
这居然是一道hard题，难以置信，就这个难度啊。
我被自己蠢哭了，把它当成ACM题，以为时间只有一秒，非要优化到O(n*log(n))。
没想到时间和空间复杂度O（n*m）就可以过了。
不说了，第一次过hard题，20分钟，直接上代码把：
class Solution {
public:
int findKthNumber(int m, int n, int k) {
if(m > n) swap(m, n);
int l = ; int r = m*n;
while(l < r){
int mid = (l+r)/;
int p = judge(m, n, k, mid);
// cout << p << " ";
if(p == ){
return mid;
}else if(p == ){
r = mid-;
}else if(p == ){
l = mid+;
}
}
return r;
}
int judge(int m, int n, int k, int mid){
int sum1 = , sum2 = ;
for(int i = ;i <= m; i++){
if(i * n <= mid){
sum2 += n;
}else{
sum2 += mid/i;
}
if(i * n < mid){
sum1 += n;
}else{
sum1 += (mid-)/i;
}
// cout << sum1 << endl;
}
cout << mid << " " << sum1 << " " << sum2 << endl;
if(sum1 < k && sum2 >= k){
return ;
}else if(sum1 >= k){
return ;
}else if(sum2 < k){
return ;
}
}
};
最新文章
- kettle之mongodb数据同步
- 编码UTF-8
- tinyxml学习4
- atitit.web 推送实现方案集合(2)---百度云,jpush 极光推送 ,个推的选型比较.o99
- Windows下移动MariaDB数据目录 (转！)
- XML的约束(schema)
- 如何使用Native Messaging API 打开window程序
- 对石家庄铁道大学官网UI设计的分析
- Kernel Panic常见原因以及解决方法
- ROS理解roslaunch命令
- git for windows+TortoiseGit客户端的使用二
- 让你成功安装vscode中go的相关插件
- PyQt IDE 环境搭建
- go语言nsq源码解读七 lookup_protocol_v1.go
- Java(15) 多态
- dataframe的select传入不定参数
- Java8：Lambda表达式增强版Comparator和排序
- JavaWeb连接SQLServer数据库并完成一个登录界面及其功能设计。
- Mysql 死锁分析学习
- 新建gradle文件