面试问题：三个数组和O（N * N） [英] Interview question: three arrays and O(N*N)

问题描述

假设我们有三长度的数组的的 N 的包含任意数字类型的长。然后，我们得到了许多的的 M 的（同一类型的），我们的使命是选择三个号码的的 A 的 ， B 的和的 C 的从每个阵列（即 A 应的从第一个数组回升， B 的从第二个和的 C 的从第三）这样的总和的的 A + B + C = M 的

Assume we have three arrays of length N which contain arbitrary numbers of type long. Then we are given a number M (of the same type) and our mission is to pick three numbers A, B and C one from each array (in other words A should be picked from first array, B from second one and C from third) so the sum A + B + C = M.

问：可能我们选择这三个数字，最终随着时间的复杂性的 O（N ² ）的

Question: could we pick all three numbers and end up with time complexity of O(N²)?

图：

数组是：

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的第三的。

And M we've been given is 19. Then our choice would be 8 from first, 4 from second and 7 from third.

推荐答案

这可以为O完成（1）空间和O（N ² ）的时间。

This can be done in O(1) space and O(N²) time.

首先让我们解决一个简单的问题：
给定两个数组 A 和 B 挑选每一个元素使他们的总和等于给定数 K 。

First lets solve a simpler problem:
Given two arrays A and B pick one element from each so that their sum is equal to given number K.

排序都这需要O阵列（NlogN）。
以指针我和Ĵ让我指向数组的开始 A 和Ĵ指向 B的结束。
寻找总和 A [I] + B [J] ，并用 K

Sort both the arrays which takes O(NlogN).
Take pointers i and j so that i points to the start of the array A and j points to the end of B.
Find the sum A[i] + B[j] and compare it with K

• 如果 A [I] + B [J] ==氏/ code>我们已经找到 这对 A [1] 和 B [J]
• 如果 A [I] + B [J] LT;氏/ code>，我们需要 增加的总和，因此增加我。
• 如果 A [I] + B [J] GT;氏/ code>，我们需要 下降的总和，因此减Ĵ。

• if A[i] + B[j] == K we have found the pair A[i] and B[j]
• if A[i] + B[j] < K, we need to increase the sum, so increment i.
• if A[i] + B[j] > K, we need to decrease the sum, so decrement j.

找到对排序后的这个过程需要O（N）。

This process of finding the pair after sorting takes O(N).

现在让我们最初的问题。我们已经得到了第三排，现在把它叫做 C 。

Now lets take the original problem. We've got a third array now call it 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 时间和我们每做一Ø运行（N）的操作使得整个算法O（N ² ）

The outer loop runs N times and for each run we do a O(N) operation making the entire algorithm O(N²).

这篇关于面试问题：三个数组和O（N * N）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！