Kth Smallest Product of Two Sorted Arrays in Java

给定两个已排序的整数数组 nums1 和 nums2，以及一个整数 k。任务是确定 nums1[i] * nums2[j] 的第 k 个（从 0 开始计数）最小乘积，其中 0 <= i < nums1.length 且 0 <= j < nums2.length。

示例 1

输入

nums1 = [2,8], nums2 = [3,4,5], k = 4

输出 24

解释： 可能有四个小于或等于 24 的乘积

2 * 3 = 6

2 * 4 = 8

2 * 5 = 10

8 * 3 = 24

示例 2

输入

nums1 = [-5,-3,0,3], nums2 = [2,4], k = 6

输出 0

解释： 有 6 个可能的小于或等于 0 的乘积

-5*2=-10

-5*4=-20

-3*2=-6

-3*4=-12

0*2=0

0*4=0

示例 3

输入

nums1 = [-6,-4,-3,0,1,3,4,7], nums2 = [-5,2,3,4], k = 40

输出 147

暴力破解法

算法

步骤 1： 要存储组件 A 和 B 的乘积，请创建一个名为 products 的空列表。

步骤 2： 遍历 A 中的每个元素。对于 A 中的每个元素 an，遍历 B 中的每个元素 b，并将 a * b 添加到 products 中。

步骤 3： 使用 Collections.Sort 对乘积列表进行升序排序。

步骤 4： 转到 products 中的索引 k-1 以获取第 k 个最小乘积。返回 products.get(k - 1) 作为结果。

实施

上述步骤的实现如下

文件名： KthSmallestProduct.java

输出

 
Kth Smallest Product is: 6   

复杂度分析

时间复杂度： O(m⋅log (m⋅n)) 是时间复杂度。生成所有乘积需要 O(m⋅n)，排序它们需要 O(m⋅log (m⋅n))。

空间复杂度： 需要 O(m⋅n) 的空间来将所有 m⋅n 个乘积存储在 products 列表中。

最优方法

我们可以利用二分查找潜在的乘积值来找到最佳答案。

算法

步骤 1： 首先，将最小乘积（A[0] * B[0]）设为左边界，将最大乘积（A[m-1] * B[n-1]）设为右边界。这里，m 和 n 分别代表 A 和 B 的长度。

步骤 2： 当 left 小于 right 时

通过取 left 和 right 的中间值来确定 mid。使用辅助函数 countLessThanOrEqual 来确定有多少个项小于或等于 mid。如果计数小于 k，则将 left 调整为 mid + 1，否则将 right 调整为 mid。循环结束后，第 k 个最小乘积将在左侧。

步骤 3： 对于 A 中的每个元素，计算小于或等于 mid 的乘积的数量。

• 步骤 3.1： 如果 a > 0，则使用上界来计算 B 中小于或等于 x/a 的项的数量。
• 步骤 3.2： 如果 a < 0，则使用下界来计算 B 中大于或等于 x/a 的项的数量。
• 步骤 3.3： 由于所有与零相乘的乘积都为零，因此如果 a == 0 且 x >= 0，则添加 B 的长度。

返回 A 中 an 的总数。

步骤 4： 查找 B 中第一个大于 x 的元素的位置。二分查找 B 中的边界，上界。下界确定 B 中至少存在 x 个元素的第一个位置。

实施

上述步骤的实现如下

文件名： KthSmallestProduct1.java

输出

 
Kth Smallest Product is: 6   

复杂度分析

时间复杂度： O((m+n)log(最大范围)) 对乘积范围进行二分查找需要 O(log(最大范围))，计算小于或等于 mid 的元素需要 O(m+n)。

空间复杂度： O(1) 只使用了固定量的额外空间。