Hard

题目描述

给定两个 0 索引 的有序整数数组 nums1 和 nums2 以及一个整数 k，返回所有乘积 nums1[i] * nums2[j] 中第 k 小的乘积（1 索引），其中 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 * 10^4
  • -10^5 <= nums1[i], nums2[j] <= 10^5
  • 1 <= k <= nums1.length * nums2.length
  • nums1 和 nums2 都已排序

解题思路

这是一道关于在两个有序数组的笛卡尔积中找第 k 小元素的问题。关键思路是使用二分搜索答案。

首先分析乘积的特点：由于数组中可能包含负数、0、正数，我们需要考虑不同情况下乘积的排序规律：

  • 负数 × 负数 = 正数（较大的负数乘积较小）
  • 负数 × 正数 = 负数（绝对值较大的负数乘积较小）
  • 0 × 任何数 = 0
  • 正数 × 正数 = 正数（较小的正数乘积较小）

核心算法是二分搜索：在可能的乘积范围内二分查找，对于每个候选值 mid，计算有多少个乘积小于等于 mid。如果个数 >= k，说明答案可能是 mid 或更小；否则答案一定比 mid 大。

计算小于等于某个值的乘积个数时，需要根据 nums1[i] 的符号分情况讨论：

  • 如果 nums1[i] > 0：在 nums2 中找最大的 j 使得 nums1[i] * nums2[j] <= mid
  • 如果 nums1[i] < 0：在 nums2 中找最小的 j 使得 nums1[i] * nums2[j] <= mid
  • 如果 nums1[i] = 0：只要 mid >= 0 就贡献 nums2.length 个

时间复杂度为 O((m+n) * log(max_value))，其中 max_value 是乘积的可能范围。

代码实现

class Solution {
public:
    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {
        long long left = -1e10, right = 1e10;
        
        auto countLE = [&](long long target) -> long long {
            long long count = 0;
            for (int a : nums1) {
                if (a > 0) {
                    // a * b <= target => b <= target / a
                    long long maxB = target / a;
                    count += upper_bound(nums2.begin(), nums2.end(), maxB) - nums2.begin();
                } else if (a < 0) {
                    // a * b <= target => b >= target / a (since a < 0)
                    long long minB = (target + a - 1) / a; // ceiling division for negative
                    count += nums2.end() - lower_bound(nums2.begin(), nums2.end(), minB);
                } else {
                    // a == 0, product is 0
                    if (target >= 0) count += nums2.size();
                }
            }
            return count;
        };
        
        while (left < right) {
            long long mid = left + (right - left) / 2;
            if (countLE(mid) >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
};

class Solution:
    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:
        import bisect
        
        left, right = -10**10, 10**10
        
        def count_le(target):
            count = 0
            for a in nums1:
                if a > 0:
                    # a * b <= target => b <= target // a
                    max_b = target // a
                    count += bisect.bisect_right(nums2, max_b)
                elif a < 0:
                    # a * b <= target => b >= ceil(target / a)
                    min_b = -((-target) // (-a))  # ceiling division
                    count += len(nums2) - bisect.bisect_left(nums2, min_b)
                else:
                    # a == 0, product is 0
                    if target >= 0:
                        count += len(nums2)
            return count
        
        while left < right:
            mid = (left + right) // 2
            if count_le(mid) >= k:
                right = mid
            else:
                left = mid + 1
        
        return left

public class Solution {
    public long KthSmallestProduct(int[] nums1, int[] nums2, long k) {
        long left = -100000000000L, right = 100000000000L;
        
        while (left < right) {
            long mid = left + (right - left) / 2;
            if (CountLE(nums1, nums2, mid) >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
    
    private long CountLE(int[] nums1, int[] nums2, long target) {
        long count = 0;
        foreach (int a in nums1) {
            if (a > 0) {
                long maxB = target / a;
                count += BinarySearchRight(nums2, maxB);
            } else if (a < 0) {
                long minB = (target + a - 1) / a;
                count += nums2.Length - BinarySearchLeft(nums2, minB);
            } else {
                if (target >= 0) count += nums2.Length;
            }
        }
        return count;
    }
    
    private int BinarySearchRight(int[] arr, long target) {
        int left = 0, right = arr.Length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    private int BinarySearchLeft(int[] arr, long target) {
        int left = 0, right = arr.Length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

var kthSmallestProduct = function(nums1, nums2, k) {
    let left = -1e11, right = 1e11;
    
    const countLE = (target) => {
        let count = 0;
        for (let a of nums1) {
            if (a > 0) {
                let maxB = Math.floor(target / a);
                count += binarySearchRight(nums2, maxB);
            } else if (a < 0) {
                let minB = Math.ceil(target / a);
                count += nums2.length - binarySearchLeft(nums2, minB);
            } else {
                if (target >= 0) count += nums2.length;
            }
        }
        return count;
    };
    
    const binarySearchRight = (arr, target) => {
        let left = 0, right = arr.length;
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    };
    
    const binarySearchLeft = (arr, target) => {
        let left = 0, right = arr.length;
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    };
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (countLE(mid) >= k) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
二分搜索答案O(log(V))O(1)
计算小于等于目标值的个数O((m+n) × log(n))O(1)
总体O((m+n) × log(n) × log(V))O(1)

其中 m 和 n 分别为两个数组的长度，V 为乘积的值域范围（约为 10^11）。

相关题目