arrays - 找到具有给定约束的最大总和的对

Question

我最近在一次求职面试中被要求找出具有给定约束的两个数组的最大和。这个问题的措辞不同，但归结为我上面所说的。没有提到元素是不同的，或者数组被排序。

例子:

A = [2000, 3000, 4000, 5000]
B = [6000, 5000, 4000, 1000]
Constraint: A[i] + B[j] <= 7000
Expected Result: (A[0], B[1]), (A[1], B[2])

请注意，这与 Find the pair across 2 arrays with kth largest sum 不是同一个问题因为约束。

暴力解法是取两个数组的笛卡尔积，计算每对的和，过滤掉大于 7000 的，排序，取顶部相等的值。时间复杂度为 O(n²)。我们可以做得更好吗？

Answer 1

一开始，您应该对两个数组进行排序。然后你可以使用这个迭代:

for every number in A:
    perform binary search to find biggest element in B lower than 7000-A

您在二进制搜索中找到的数字是数组 A 中当前数字配对的最佳数字。您可以取这些值中的最大值(对于数组 A 上的所有迭代)。

二分搜索在 O(logN) 时间内运行，因此此迭代在 O(NlogN) 时间内运行，排序也在 O(NlogN) 时间内运行。您可以使用变量更改 7000。