目录
题目要求
思路：二分
- 每行每列都是单调递增的；
- 统计每行（列）中小于
m
i
d
mid
mid的数记les，等于
m
i
d
mid
mid的数记equ，设当前行号为
i
i
i（行列等价，此处用行做基准论述）：
- 当前行（列）最大值为
i
×
m
itimes m
i×m；
- 若
i
×
m
<
m
i
d
itimes m
- 若
i
×
m
>
=
m
i
d
itimes m>= mid
i×m>=mid，判断是否有于
m
i
d
mid
mid相等的 数分情况处理。
- 然后根据
k
k
k和
c
n
t
cnt
cnt的关系移动左右指针。
- 实现中简化判断，直接取
m
i
d
/
i
mid/i
mid/i和当前行元素个数中较小的一个。
Java
class Solution {
public int findKthNumber(int m, int n, int k) {
int mi = Math.min(m, n), ma = Math.max(m, n);
int l = 1, r = m * n;
while(l < r) {
int mid = l + r >> 1, cnt = 0;
for(int i = 1; i <= mi; i++)
cnt += Math.min(mid / i, ma);
if(cnt >= k)
r = mid;
else
l = mid + 1;
}
return r;
}
}
- 时间复杂度：
O
(
min
(
n
,
m
)
×
log
m
n
)
O(min(n,m) times log mn)
O(min(n,m)×logmn)
- 空间复杂度：
O
(
1
)
O(1)
O(1)
C++
class Solution {
public:
int findKthNumber(int m, int n, int k) {
int mi = min(m, n), ma = max(m, n);
int l = 1, r = m * n;
while(l < r) {
int mid = l + r >> 1, cnt = 0;
for(int i = 1; i <= mi; i++)
cnt += min(mid / i, ma);
if(cnt >= k)
r = mid;
else
l = mid + 1;
}
return r;
}
};
- 时间复杂度：
O
(
min
(
n
,
m
)
×
log
m
n
)
O(min(n,m) times log mn)
O(min(n,m)×logmn)
- 空间复杂度：
O
(
1
)
O(1)
O(1)
Rust
impl Solution {
pub fn find_kth_number(m: i32, n: i32, k: i32) -> i32 {
let(mut l, mut r) = (1, m * n + 1);
while l < r {
let(mid, mut cnt) = (l + ((r - l) >> 1), 0);
for i in 1..=m {
cnt += n.min(mid / i);
}
if cnt >= k {
r = mid;
}
else{
l = mid + 1;
}
}
r
}
}
总结
二分的应用题，最开始并没有意识到问题的二段性，遍历思路就很简单了。
