力扣2040两个有序数组的第K小乘积

题目：2040. 两个有序数组的第 K 小乘积 - 力扣（LeetCode）

解法一：二分加二分

有数据范围可知，答案在-1e10到1e10之间，两个数组都是有序的，直接进行相乘是会超时的，所以我们可以通过二分进行查找答案，但这里细节很多，要注意。如果此时中间值为count,我们要寻找小于等于count的元素个数

先固定nums1的值nums[i]=k

k>=0时，可得到nums[i]*nums[j]是非递减的。

k<0时，可得到nums[i]*nums[j]是非递增的。

 

public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {int n=nums1.length;long left=(long)-1e10;long right=(long)1e10;while(left<=right) {long count=0;long mid=(right-left)/2+left;for(int i=0;i<n;i++) {count+=f(nums2,nums1[i],mid);}if(count<k) {left=mid+1;} else {right=mid-1;} }return left;}public long f(int[] nums2,long x,long m) {int left=0;int right=nums2.length-1;while(left<=right) {int mid=(right-left)/2+left;long tmp=(long)nums2[mid]*x;if((x>=0&&tmp>m)||(x<0&&tmp<=m)) {right=mid-1;} else {left=mid+1;}}if(x>=0) {return left;} else {return nums2.length-left;}}

 在第一个二分的时候，不可以count=k的时候就直接跳出循环，因为假设满足条件的结果为x,而k+1大的数为y，count=k的时候，只是满足了mid在[x,y)的区间内，并非是最终的结果，最终结果是要不断往左边进行逼近，所以满足count>=k时，right往左边逼近，而left不变，最终left就正好是结果，而right就在left的左边一位。

第二个方法用于计算nums1[i]=x的时候，与nums2[j]乘积小于m的个数，也与上一个二分类似

满足条件的下标并不是只有一个，所以在非递减的情况下，要往右逼近，非递增则相反，但是这里最终的结果需要的是满足条件的个数，而非下标，所以x>=0返回的是left,而x<0返回length-left;相当于各自位置的旁边一个位置，弥补了下标从0开始导致的个数不对。

解法二：二分加分治

在第一部分二分的基础上，将两个数组分别分为负数部分和非负数部分，在计算count数量的时候，分情况进行讨论即可。

public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {int n1=nums1.length,n2=nums2.length;int pos1=0;int pos2=0;while(pos1<n1&&nums1[pos1]<0) {pos1++;}while(pos2<n2&&nums2[pos2]<0) {pos2++;}long left=-(long)1e10,right=(long)1e10;while(left<=right) {long mid=(left+right) /2;long count=0;//i1递增nums1的负区间，i2递减nums2的负区间//如果i1的中的数乘以i2大于mid,那么i1的这个数乘以i2及以前的都不会满足，直接跳过i1即可//如果小于，那么i1及pos1以前的数乘以i2的数，都可以满足，加上pos1-i1;int i1=0,i2=pos2-1;while(i1<pos1&&i2>=0) {if((long)nums1[i1]*nums2[i2]>mid) {i1++;} else {count+=pos1-i1;i2--;}}//i1标识nums1的正区间，i2表示nums2的正区间//i1*i2大于mid,i1及以后都会大于，i2--;//小于等于的时候，i2及以前的值乘i1都满足i1=pos1;i2=n2-1;while(i1<n1&&i2>=pos2) {if((long)nums1[i1]*nums2[i2]>mid) {i2--;} else {count+=i2-pos2+1;i1++;}}//i1为nums1的正区间，i2为nums2的负区间//这里必须是两个区间都进行递增,要区别前面两个//i1*i2>mid时，i1只能向右移动//<mid时，只能保证i1的右边是满足的，所以i2向右移动i1=pos1;i2=0;while(i1<n1&&i2<pos2) {if((long)nums1[i1]*nums2[i2]>mid) {i1++;} else {count+=n1-i1;i2++;}}i1=0;i2=pos2;while(i1<pos1&&i2<n2) {if((long)nums1[i1]*nums2[i2]>mid) {i2++;} else {count+=n2-i2;i1++;}}if(count<k) {left=mid+1;} else {right=mid-1;}}return left;}