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

问题描述

假设我们有三个长度为N的数组，其中包含long类型的任意数字.然后我们得到一个数字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) 的两个数组进行排序.
取指针i 和j 使i 指向数组A 和 的开始>j 指向 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] == K 我们已经找到A[i] 和 B[j]
对
• if A[i] + B[j] ，我们需要增加总和，所以增加 i.
• if A[i] + B[j] >K，我们需要减少总和，因此减少 j.

• 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 次，每次运行我们都进行 O(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屋！