The solution utilizes a binary search method on the product values rather than the indices of the arrays. Given two sorted arrays, the smallest and largest possible products are first identified. These products form the range for the binary search. The binary search's middle value is then used to count the products that are smaller than this middle value, by checking how many elements from nums2 are less than the division of this middle value by each element in nums1. This count determines if the k-th smallest product is greater or smaller than the middle value, adjusting the search range accordingly. The process continues until the exact k-th smallest product is located.
时间复杂度: O(log(maxProduct - minProduct) * log(len(nums2)) * len(nums1))
空间复杂度: O(len(nums1) + len(nums2))
from numpy import array, sum
class Solution:
def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:
nums1, nums2 = array(nums1), array(nums2) # Convert lists to numpy arrays
LEN2 = nums2.size # Length of the second array
above = nums1[nums1 > 0] # Subarray of positive elements in nums1
below = nums1[nums1 < 0] # Subarray of negative elements in nums1
zeroCount = sum(nums1 == 0) # Count of zeros in nums1
# Calculate potential minimum and maximum products from boundary elements
minmax = [nums1[0] * nums2[0], nums1[0] * nums2[-1], nums1[-1] * nums2[0], nums1[-1] * nums2[-1]]
left, right = int(min(minmax)), int(max(minmax) + 1) # Set initial binary search bounds
while (left < right): # Binary search loop
n = (left + right) >> 1 # Middle product value
if (sum(nums2.searchsorted(n / above)) + # Count of products less than 'n' with positive nums1 elements
LEN2 * below.size - sum(nums2.searchsorted(n / below, "right")) + # Adjust count for negative nums1 elements
(zeroCount * LEN2 if n > 0 else 0)) < k: # Include zero product counts if 'n' allows
left = n + 1 # Adjust search range
else:
right = n
return left - 1 # Since left is incremented one past the correct answer