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

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