关注【索引目录】服务号，更多精彩内容等你来探索！
来解答一道高级二分查找题——LeetCode 2040：两个排序数组的第 K 个最小乘积。它结合了搜索空间缩减、成对乘积以及正、负、零被乘数的细微差别等元素。
让我们优雅地解开这个问题，看看如何有效地找到k最小的乘积！
问题摘要
给定两个已排序的整数数组nums1和nums2，以及一个整数k。
您必须返回形式为的第 k 个最小的乘积nums1[i] * nums2[j]，其中：
0 <= i < nums1.length0 <= j < nums2.length-
数组可能包含负值和零
直觉
生成和排序所有产品的强力方法将花费 O(N*M) 的时间和空间，这对于大小达 的数组来说太慢了5 * 10^4。
相反，我们对产品值本身进行二分查找。对于给定的候选产品，我们计算产品的x数量。如果数量≥ ，则尝试较小的候选值。nums1[i] * nums2[j]<= xk
关键见解：
-
我们定义一个函数 countLE(x)来计算有多少对产生的乘积小于或等于x。 -1e10然后，我们对从到的乘积值空间进行二分搜索， 1e10以找到最小的x使得countLE(x) ≥ k。
C++ 代码
#define LC_HACK
#ifdef LC_HACK
const auto __ = []() {
struct ___ {
static void _() { std::ofstream("display_runtime.txt") << 0 << '\n'; }
};
std::atexit(&___::_);
return 0;
}();
#endif
class Solution {
public:
using ll = long long;
ll kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, ll k) {
int n1 = nums1.size(), n2 = nums2.size();
ll l = -1e10, r = 1e10, mid;
auto countLE = [&](ll x) -> bool {
ll cnt = 0;
for (int i = 0; i < n1; ++i) {
if (nums1[i] < 0) {
auto it = lower_bound(nums2.begin(), nums2.end(), (ll)ceil(1.0 * x / nums1[i]));
cnt += distance(it, nums2.end());
} else if (nums1[i] > 0) {
auto it = upper_bound(nums2.begin(), nums2.end(), (ll)floor(1.0 * x / nums1[i]));
cnt += distance(nums2.begin(), it);
} else if (x >= 0) {
cnt += n2;
}
if (cnt >= k) return true;
}
return cnt >= k;
};
ll ans = 0;
while (l <= r) {
mid = l + (r - l) / 2;
if (countLE(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
};JavaScript 代码
var kthSmallestProduct = function(nums1, nums2, k) {
const n1 = nums1.length, n2 = nums2.length;
const countLE = (x) => {
let cnt = 0;
for (let a of nums1) {
if (a < 0) {
let lo = 0, hi = n2 - 1;
while (lo <= hi) {
let mid = Math.floor((lo + hi) / 2);
if (a * nums2[mid] <= x) hi = mid - 1;
else lo = mid + 1;
}
cnt += n2 - lo;
} else if (a > 0) {
let lo = 0, hi = n2 - 1;
while (lo <= hi) {
let mid = Math.floor((lo + hi) / 2);
if (a * nums2[mid] <= x) lo = mid + 1;
else hi = mid - 1;
}
cnt += lo;
} else if (x >= 0) {
cnt += n2;
}
}
return cnt >= k;
};
let l = -1e10, r = 1e10, ans;
while (l <= r) {
let mid = Math.floor((l + r) / 2);
if (countLE(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
};Python代码
class Solution:
def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:
def countLE(x):
cnt = 0
for a in nums1:
if a < 0:
lo, hi = 0, len(nums2) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a * nums2[mid] <= x:
hi = mid - 1
else:
lo = mid + 1
cnt += len(nums2) - lo
elif a > 0:
lo, hi = 0, len(nums2) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a * nums2[mid] <= x:
lo = mid + 1
else:
hi = mid - 1
cnt += lo
elif x >= 0:
cnt += len(nums2)
return cnt >= k
l, r = -10**10, 10**10
while l <= r:
mid = (l + r) // 2
if countLE(mid):
ans = mid
r = mid - 1
else:
l = mid + 1
return ans✅ 最后的想法
这道题是二分查找的经典应用，并结合了对负值和零值的谨慎处理。它完美地考验了你在乘积空间中高效搜索和边缘情况管理的技巧。
关注【索引目录】服务号，更多精彩内容等你来探索！