给你两个 从小到大排好序 且下标从 0 开始的整数数组 nums1 和 nums2 以及一个整数 k
请你返回第 k (从 1 开始编号)小的 nums1[i] * nums2[j] 的乘积
1. 二分查找
class Solution {
public:
typedef long long ll;
long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {
//时间复杂度O(m*n*10glog10)
vector<int> p1,p2,n1,n2;
//将正数负数分开
for(int x:nums1) (x<0)?n1.push_back(x):p1.push_back(x); //n存储负数,p存储正数
for(int x:nums2) (x<0)?n2.push_back(x):p2.push_back(x);
ll l=-1e10,r=1e10; //初始化左右边界
while(l<r){
ll m=(l+r)>>1;
ll cur=0;//计数
//找满足乘积小于等于mid的个数
for(int i=0,j=p2.size()-1;i<p1.size();i++){ //正数和正数
while(j>=0&&1LL*p1[i]*p2[j]>m) j--; //指针前移,j及之前的坐标都满足要求,总个数为j+1
cur+=j+1;
}
for(int i=0,j=0;i<p1.size();i++){ //正数和负数
while(j<n2.size()&&1LL*p1[i]*n2[j]<=m) j++; //指针后移,j之前的坐标都满足要求,总个数为j
cur+=j;
}
for(int i=0,j=n2.size()-1;i<n1.size();i++){//负数和负数
while(j>=0&&1LL*n1[i]*n2[j]<=m) j--; //指针前移,j之后为满足条件的个数,前面有j+1个数,减去
cur+=n2.size()-(j+1); //加上后面的个数
}
for(int i=0,j=0;i<n1.size();i++){//负数和正数
while(j<p2.size()&&1LL*n1[i]*p2[j]>m) j++; //指针后移,j及之后的为满足条件的个数,前面有j个数,减去
cur+=p2.size()-j;
}
if(cur<k) l=m+1;//不满足条件
else r=m;
}
return r;
}
};
2. 二分 + 二分
优化方法一中对另一个数组的暴力查找
只优化了正数和正数的查找,貌似性能更差,不再继续优化
class Solution {
public:
typedef long long ll;
long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {
//时间复杂度O(m*n*10glog10)
vector<int> p1,p2,n1,n2;
//将正数负数分开
for(int x:nums1) (x<0)?n1.push_back(x):p1.push_back(x); //n存储负数,p存储正数
for(int x:nums2) (x<0)?n2.push_back(x):p2.push_back(x);
ll l=-1e10,r=1e10; //初始化左右边界
while(l<r){
ll m=(l+r)>>1;
ll cur=0;//计数
//找满足乘积小于等于mid的个数
for(int i=0,j=p2.size()-1;i<p1.size();i++){ //正数和正数
if(p1[i]==0) j = m>=0?p2.size():0;
else {
double val = (double)m/p1[i];
auto leftbound = upper_bound(p2.begin(), p2.end(), val);
j = leftbound - p2.begin();
}
cur+=j;
}
for(int i=0,j=0;i<p1.size();i++){ //正数和负数
while(j<n2.size()&&1LL*p1[i]*n2[j]<=m) j++; //指针后移,j之前的坐标都满足要求,总个数为j
cur+=j;
}
for(int i=0,j=n2.size()-1;i<n1.size();i++){//负数和负数
while(j>=0&&1LL*n1[i]*n2[j]<=m) j--; //指针前移,j之后为满足条件的个数,前面有j+1个数,减去
cur+=n2.size()-(j+1); //加上后面的个数
}
for(int i=0,j=0;i<n1.size();i++){//负数和正数
while(j<p2.size()&&1LL*n1[i]*p2[j]>m) j++; //指针后移,j及之后的为满足条件的个数,前面有j个数,减去
cur+=p2.size()-j;
}
if(cur<k) l=m+1;//不满足条件
else r=m;
}
return r;
}
};
标签:p2,乘积,int,long,nums1,vector,有序,数组,cur
From: https://www.cnblogs.com/929code/p/17442047.html