class Solution {
public:
long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {
}
};
2040. 两个有序数组的第 K 小乘积
给你两个 从小到大排好序 且下标从 0 开始的整数数组nums1 和 nums2 以及一个整数 k ，请你返回第 k （从 1 开始编号）小的 nums1[i] * nums2[j] 的乘积，其中 0 <= i < nums1.length 且 0 <= j < nums2.length 。
示例 1：
输入：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：
输入：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：
输入：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 。
提示：
1 <= nums1.length, nums2.length <= 5 * 104-105 <= nums1[i], nums2[j] <= 1051 <= k <= nums1.length * nums2.lengthnums1 和 nums2 都是从小到大排好序的。原站题解
python3 解法, 执行用时: 3720 ms, 内存消耗: 23.9 MB, 提交时间: 2023-09-04 17:27:57
'''
二分答案的题，和乘法表的题目一样，子问题是，乘积不超过 x 能找到多少对来完成，
那么最小的 x 且满足至少有 k 对的情况就是答案。
注意数字不是正数，不等号的处理。如果是 0，那么不等式不是一元一次不等式，
如果是负数，不等号要反向，另外还要注意 python 除法的取整问题。
python 中的 // 是向下取整，但是向上取整，为了方便，直接浮点除法 + math.ceil 调用实现。
'''
class Solution:
def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:
if len(nums1) >= len(nums2): nums1, nums2 = nums2, nums1 # nums2取长的
a, b, c, d = nums1[0] * nums2[0], nums1[0] * nums2[-1], nums1[-1] * nums2[-1], nums1[-1] * nums2[0]
mn, mx = min(a, b, c, d), max(a, b, c, d)
while mn < mx:
mid = (mn + mx) >> 1
cnt = 0
for num in nums1:
if num > 0:
cnt += bisect.bisect_right(nums2, mid // num)
elif num == 0:
cnt += len(nums2) if mid >= 0 else 0
else:
cnt += len(nums2) - bisect.bisect_left(nums2, math.ceil(mid / num))
if cnt < k:
mn = mid + 1
else:
mx = mid
return mn
golang 解法, 执行用时: 744 ms, 内存消耗: 7.4 MB, 提交时间: 2023-09-04 17:20:54
// 分类讨论 + 二分答案
func kthSmallestProduct(nums1 []int, nums2 []int, K int64) int64 {
n1, n2 := len(nums1), len(nums2)
p10 := sort.SearchInts(nums1, 0)
p11 := sort.SearchInts(nums1, 1)
p20 := sort.SearchInts(nums2, 0)
p21 := sort.SearchInts(nums2, 1)
neg := p10*(n2-p21) + p20*(n1-p11) // 负数乘积个数
pos := p10*p20 + (n1-p11)*(n2-p21) // 正数乘积个数
zero := n1*n2 - neg - pos // 乘积为 0 的个数
pos1, pos2 := nums1[p11:], nums2[p21:]
neg1, neg2 := nums1[:p10], nums2[:p20]
for i := range neg2 {
neg2[i] = -neg2[i]
}
for i, n := 0, len(neg2); i < n/2; i++ {
neg2[i], neg2[n-1-i] = neg2[n-1-i], neg2[i]
}
k := int(K)
if k <= neg {
k = neg - k + 1
return int64(-sort.Search(1e10, func(t int) bool {
cnt := 0
for _, v := range pos1 { cnt += sort.SearchInts(neg2, t/v+1) } // 也可以用双指针，这里为了方便直接二分
for _, v := range neg1 { cnt += sort.SearchInts(pos2, t/-v+1) }
return cnt >= k
}))
}
if k <= neg+zero {
return 0
}
k -= neg + zero
return int64(sort.Search(1e10, func(t int) bool {
cnt := 0
for _, v := range pos1 { cnt += sort.SearchInts(pos2, t/v+1) }
for _, v := range neg1 { cnt += sort.SearchInts(neg2, t/-v+1) }
return cnt >= k
}))
}