Trace
两个有序数组的第K小乘积
传送门：https://leetcode-cn.com/problems/kth-smallest-product-of-two-sorted-arrays/
给你两个 从小到大排好序 且下标从 0 开始的整数数组 nums1 和 nums2 以及一个整数 k ，请你返回第 k （从 1 开始编号）小的 nums1[i] * nums2[j] 的乘积，其中 0 <= i < nums1.length 且 0 <= j < nums2.length。
示例 1：
1
2
3
4
5
6
| 输入：nums1 = [2,5], nums2 = [3,4], k = 2
输出：8
解释：第 2 小的乘积计算如下：
- nums1[0] * nums2[0] = 2 * 3 = 6
- nums1[0] * nums2[1] = 2 * 4 = 8
第 2 小的乘积为 8 。
|
示例 2：
1
2
3
4
5
6
7
8
9
10
| 输入：nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6
输出：0
解释：第 6 小的乘积计算如下：
- nums1[0] * nums2[1] = (-4) * 4 = -16
- nums1[0] * nums2[0] = (-4) * 2 = -8
- nums1[1] * nums2[1] = (-2) * 4 = -8
- nums1[1] * nums2[0] = (-2) * 2 = -4
- nums1[2] * nums2[0] = 0 * 2 = 0
- nums1[2] * nums2[1] = 0 * 4 = 0
第 6 小的乘积为 0 。
|
示例 3：
1
2
3
4
5
6
7
| 输入：nums1 = [-2,-1,0,1,2], nums2 = [-3,-1,2,4,5], k = 3
输出：-6
解释：第 3 小的乘积计算如下：
- nums1[0] * nums2[4] = (-2) * 5 = -10
- nums1[0] * nums2[3] = (-2) * 4 = -8
- nums1[4] * nums2[0] = 2 * (-3) = -6
第 3 小的乘积为 -6 。
|
思路
二分+二分
假设$f(x)$为满足$nums1[i]$与$nums2[j] $的乘积小于等于$x$的组数，显然函数随$x$递增，可以二分。
计算满足$nums1[i]$与$nums2[j] $的乘积小于等于$x$的组数时，枚举$nums1$中的数$u$，每次固定$u$，二分$nums2$，寻找$nums2$中有多少个数满足$u*nums2[j]<=x$。
程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| class Solution {
public:
vector<int> A;
vector<int> B;
long long check(long long x){
long long cnt=0;
for(long long u:A){
if(u>0){
if(u*B[0]>x) continue;
int l=0,r=B.size()-1;
while(l<r){
int mid=(l+r+1)>>1;
if(u*B[mid]<=x){
l=mid;
}
else{
r=mid-1;
}
}
cnt+=l+1;
}
else if(u<0){
if(u*B[B.size()-1]>x) continue;
int l=0,r=B.size()-1;
while(l<r){
int mid=(l+r)>>1;
if(u*B[mid]<=x){
r=mid;
}
else{
l=mid+1;
}
}
cnt+=B.size()-l;
}
else if(u==0){
if(x>=0){
cnt+=B.size();
}
}
}
return cnt;
}
long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {
A=nums1;
B=nums2;
long long l=-1e10-10;
long long r=1e10+10;
while(l<r){
long long mid=(l+r)>>1;
if(check(mid)>=k){
r=mid;
}
else{
l=mid+1;
}
}
return l;
}
};
|
