面试问题:三个阵列和O(N*N)

Question

假设我们有三个长度为N的数组,它们包含任意数量的类型long.然后给出一个数字M(相同类型),我们的任务是从每个数组中选择三个数字A,B和C(换句话说,A 应该从第一个数组中选择,B从第二个数组中选择,C从第三个数据中选择),以使之和A + B + C = M.

问题:我们可以选择所有三个数字并最终得到O(N ²)的时间复杂度吗？

---

插图:

数组是:

1) 6 5 8 3 9 2
2) 1 9 0 4 6 4
3) 7 8 1 5 4 3

而中号,我们已经给出是19.然后我们的选择是从第一个8,从第二个4和从第三个7.

Answer 1

这可以在O(1)空间和O(N ²)时间内完成.

首先让我们解决一个更简单的问题:
给定两个数组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(N ²).

Answer 2

您可以将它减少到两个数组的类似问题,这有点着名并且具有简单的O(n)解决方案(涉及从两端迭代).

1. 排序所有数组.
2. 尝试A从第一个数组中的每个数字.
3. 发现如果最后两个数组可以给我们的数字B和C,这样B + C = M - A.

步骤2和3乘以给出O(n ^ 2)复杂度.

Answer 3

其他解决方案已经更好了,但无论如何这里是我的O(n ^ 2)时间和O(n)内存解决方案.

将数组C的所有元素插入哈希表.(时间复杂度O(n),空间O(n))取所有对(a,b),a来自A和b来自B(时间复杂度O(n ^ 2)).对于每对,检查hastable中是否存在M-(a + b)(每个查询预期的复杂度O(1)).

因此,总体时间复杂度为O(n ^ 2),并且哈希表的空间复杂度为O(n).