假设我们有三个 长度为N 的数组,其中包含long
类型的任意数字。然后我们得到一个数字 M(相同类型),我们的任务是选择三个数字 A 、B 和 C 每个数组中的一个(换句话说,A 应该从第一个数组中挑选,B从第二个数组中挑选,C/strong> 来自第三个)所以总和A + B + C = M。
问题:我们能否选择所有三个数字并以 O(N2) 的时间复杂度结束?
插图:
数组是:
1) 6 5 8 3 9 2
2) 1 9 0 4 6 4
3) 7 8 1 5 4 3
我们得到的 M 是 19。 那么我们的选择是第一个 8,第二个 4,第三个 7。
最佳答案
这可以在 O(1) 空间和 O(N2) 时间内完成。
首先让我们解决一个更简单的问题:
给定两个数组A
和 B
从每个元素中选择一个元素,使它们的总和等于给定的数字 K
.
对两个数组进行排序,时间复杂度为 O(NlogN)。
求指点i
和 j
这样i
指向数组的开头A
和 j
指向 B
的末尾.
求和A[i] + B[j]
并将其与 K
进行比较
- 如果
A[i] + B[j] == K
我们发现 一对A[i]
和B[j]
- 如果
A[i] + B[j] < K
, 我们需要 增加总和,所以增加i
. - 如果
A[i] + B[j] > K
, 我们需要 减少和,所以减少j
.
排序后找到对的过程需要 O(N)。
现在让我们来看看原来的问题。我们现在有了第三个数组,称之为 C
.
所以现在的算法是:
foreach element x in C
find a pair A[i], B[j] from A and B such that A[i] + B[j] = K - x
end for
外循环运行 N
次,对于每次运行,我们执行 O(N) 操作,使整个算法 O(N2)。
关于arrays - 面试题: three arrays and O(N*N),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3987264/