当前位置：首页 > news >正文

千问 LeetCode 2040.两个有序数组的第 K 小乘积 public long kthSmallestProduct(int[] nums1, int[] nums2, long k)

news 2026/5/2 9:20:25

你提到的题目是 LeetCode 2040. 两个有序数组的第 K 小乘积。这是一个典型的二分答案 + 分类讨论的难题。

🧠 题目简述

给定两个升序排列的整数数组 nums1 和 nums2，以及一个整数 k，要求返回所有可能乘积 nums1[i] * nums2[j] 中第 k 小的值（从 1 开始计数）。

- 数组长度可达 5 times 10^4，所以不能暴力枚举（会超时）。
- 元素范围：[-10^5, 10^5]，乘积范围约为 [-10^{10}, 10^{10}]。

✅ 解题思路：二分答案 + 计数函数

核心思想：
我们不去生成所有乘积，而是猜一个答案 mid，然后快速判断：有多少个乘积 ≤ mid？
如果这个数量 ≥ k，说明真实答案 ≤ mid；否则 > mid。于是可以二分搜索答案。

🔍 关键难点：如何高效计算 count = 满足 nums1[i] * nums2[j] = k) {
right = mid; // 第 k 小 ≤ mid
} else {
left = mid + 1;
}
}
return left;
}

// 计算有多少对 (i, j) 满足 nums1[i] * nums2[j] = 0 ? nums2.length : 0;
}

long cnt = 0;
int n = nums2.length;

if (x > 0) {
// x > 0: nums2 升序 → 乘积升序 → 找最大的 j 使得 x * nums2[j] -5，需向下取整
limit--;
}
// 找最后一个小于等于 limit 的位置（upper_bound - 1）
int lo = 0, hi = n;
while (lo = ceil(target / x) （注意除法向零取整，需调整）
long limit = target / x;
if (target % x != 0 && (target > 0) == (x > 0)) {
// 同号且有余数 → 需要向上取整（但 Java 除法向零取整）
limit++;
}
// 找第一个 >= limit 的位置
int lo = 0, hi = n;
while (lo = limit) {
hi = mid;
} else {
lo = mid + 1;
}
}
cnt = n - lo; // [lo, n) 满足
}
return cnt;
}

⚠️ 注意事项（易错点）

1. 整数除法截断问题：Java 中 -5 / 2 = -2（向零取整），但我们需要向下取整（floor division）来保证不等式正确。
- 例如：x=3, target=-5 → limit = floor(-5/3) = -2
- 可通过检查余数符号来修正。

2. 二分边界：通常用 [left, right) 或 [left, right]，保持一致即可。上面代码用的是 [left, right)。

3. 溢出：虽然 x 和 nums2[j] 是 int，但乘积可能达 1e10，所以用 long 存储中间结果。

📌 替代思路（更简洁但稍慢）

也可以不对除法做精细修正，直接在 countForX 中对 nums2 进行二分，每次计算 x * nums2[mid] 并与 target 比较（避免除法）：

private long countForX(int[] nums2, long x, long target) {
int n = nums2.length;
int left = 0, right = n - 1;
int pos = -1;

if (x >= 0) {
// 乘积非递减
while (left <= right) {
int mid = (left + right) / 2;
if (x * nums2[mid] <= target) {
pos = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return pos + 1;
} else {
// 乘积非递增
while (left <= right) {
int mid = (left + right) / 2;
if (x * nums2[mid] <= target) {
pos = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return pos == -1 ? 0 : n - pos;
}
}