What is the main approach to solve Kth Smallest Product of Two Sorted Arrays?

Use binary search over the possible product values and count how many pairs produce products less than or equal to the candidate value.

How do negative numbers affect the counting in this problem?

Negative numbers reverse the comparison direction when counting, so each case must be handled separately to maintain correct order.

Can this problem be solved with brute force?

Brute force requires generating all products, which is infeasible for large arrays; binary search on the answer space is necessary for efficiency.

Do zeros need special handling?

Yes, all zero products must be included in the count since they are neither negative nor positive, affecting the kth product position.

What pattern does GhostInterview emphasize for this problem?

Binary search over the valid answer space, splitting counting logic based on the signs of numbers to efficiently find the kth smallest product.

#2040

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

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

给你两个从小到大排好序且下标从 0 开始的整数数组 nums1 和 nums2 以及一个整数 k ，请你返回第 k （从 1 开始编号）小的 nums1[i] \* nums2[j] 的乘积，其中 0 且 0 。示例 1：输入： nums1 = [2,5], nums2 = [3,4], 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 * 10⁴
-10⁵ <= nums1[i], nums2[j] <= 10⁵
1 <= k <= nums1.length * nums2.length
nums1 和 nums2 都是从小到大排好序的。

lightbulb

解题思路

方法一：二分查找

我们可以二分枚举乘积的值 $p$ ，定义二分的区间为 $[l, r]$ ，其中 $l = -\textit{max}(|\textit{nums1}[0]|, |\textit{nums1}[n - 1]|) \times \textit{max}(|\textit{nums2}[0]|, |\textit{nums2}[n - 1]|)$ , $r = -l$ 。

对于每个 $p$ ，我们计算出乘积小于等于 $p$ 的乘积的个数，如果这个个数大于等于 $k$ ，那么说明第 $k$ 小的乘积一定小于等于 $p$ ，我们就可以将区间右端点缩小到 $p$ ，否则我们将区间左端点增大到 $p + 1$ 。

那么问题的关键就是如何计算乘积小于等于 $p$ 的乘积的个数。我们可以枚举 $\textit{nums1}$ 中的每个数 $x$ ，分类讨论：

如果 $x > 0$ ，那么 $x \times \textit{nums2}[i]$ 随着 $i$ 的增大是单调递增的，我们可以使用二分查找找到最小的 $i$ ，使得 $x \times \textit{nums2}[i] > p$ ，那么 $i$ 就是小于等于 $p$ 的乘积的个数，累加到个数 $\textit{cnt}$ 中；
如果 $x < 0$ ，那么 $x \times \textit{nums2}[i]$ 随着 $i$ 的增大是单调递减的，我们可以使用二分查找找到最小的 $i$ ，使得 $x \times \textit{nums2}[i] \leq p$ ，那么 $n - i$ 就是小于等于 $p$ 的乘积的个数，累加到个数 $\textit{cnt}$ 中；
如果 $x = 0$ ，那么 $x \times \textit{nums2}[i] = 0$ ，如果 $p \geq 0$ ，那么 $n$ 就是小于等于 $p$ 的乘积的个数，累加到个数 $\textit{cnt}$ 中。

这样我们就可以通过二分查找找到第 $k$ 小的乘积。

时间复杂度 $O(m \times \log n \times \log M)$ ，其中 $m$ 和 $n$ 分别为 $\textit{nums1}$ 和 $\textit{nums2}$ 的长度，而 $M$ 为 $\textit{nums1}$ 和 $\textit{nums2}$ 中的最大值的绝对值。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:
        def count(p: int) -> int:
            cnt = 0
            n = len(nums2)
            for x in nums1:
                if x > 0:
                    cnt += bisect_right(nums2, p / x)
                elif x < 0:
                    cnt += n - bisect_left(nums2, p / x)
                else:
                    cnt += n * int(p >= 0)
            return cnt

        mx = max(abs(nums1[0]), abs(nums1[-1])) * max(abs(nums2[0]), abs(nums2[-1]))
        return bisect_left(range(-mx, mx + 1), k, key=count) - mx

speed

复杂度分析

指标	值
时间	O((n_1 + n_2)\log C)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Binary search over the valid product range indicates efficiency over brute force enumeration.
question_mark
Handling negative and positive products separately tests problem decomposition skills.
question_mark
Expect questions about counting pairs without generating all products.

warning

常见陷阱

外企场景

error
Forgetting to split counting logic for negative, zero, and positive numbers causes incorrect results.
error
Assuming all products are positive may miscount the kth smallest for mixed-sign arrays.
error
Not handling large input ranges efficiently can exceed time limits.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Finding the kth largest product instead of smallest requires reversing comparison logic.
arrow_right_alt
Arrays not sorted require initial sorting, increasing time complexity to O(n log n) per array.
arrow_right_alt
Finding kth smallest sum instead of product changes counting and case handling.

help

常见问题

外企场景

继续练习

#2035 将数组分成两个数组并最小化数组和的差 #2054 两个最好的不重叠活动 #2055 蜡烛之间的盘子