面试问题:三个数组和O(N * N)

假设我们有三个长度为N的数组,其中包含任意长度的数字。 然后我们给出一个M (相同types),我们的任务是从每个数组中select三个数字ABC (换句话说, A 应该从第一个数组中挑选出来, B从第二个数组中挑选出来, C从第三个)所以总和A + B + C = M。

问题:我们可以select所有三个数字,最终的时间复杂度为O(N 2吗?


插图:

数组是:

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

而我们得到的是19 。 那么我们的select是从第一个8 ,第二个4 ,第三个7

这可以在O(1)空间和O(N 2 )时间完成。

首先让我们解决一个更简单的问题:
给定两个数组AB从中select一个元素,使它们的和等于给定的数字K

对两个数组进行sorting(OlogN)。
以指针iji指向数组A的开始, j指向B的结尾。
求和A[i] + B[j]并将其与K进行比较

  • 如果A[i] + B[j] == K我们已经find了A[i]B[j]
  • 如果A[i] + B[j] < K ,我们需要增加总和,所以增加i
  • 如果A[i] + B[j] > K ,我们需要减小和,所以减lessj

sorting后find这对的过程需要O(N)。

现在让我们把原来的问题。 我们有第三个数组,现在称之为C

所以现在的algorithm是:

 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)操作,使得整个algorithmO(N 2 )。

你可以把它减less到两个数组的类似问题,这是有名的,并有简单的O(n)解决scheme(涉及从两端迭代)。

  1. sorting所有数组。
  2. 从第一个数组中尝试每个数字A一次。
  3. 查找最后两个数组是否可以给我们数字BC ,使得B + C = M - A

步骤2和步骤3相乘给我们O(n ^ 2)的复杂性。

其他的解决scheme已经更好了,但是这里是我的O(n ^ 2)时间和O(n)内存解决scheme。

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

所以,总体时间复杂度为O(n ^ 2),散列表的空间复杂度为O(n)。

哈希最后的列表。 做这个的时间是O(N)在这个特定的列表,但是这将被添加到下一个阶段。

下一个阶段是为他们的前两行创build一个“matrix”。 然后在哈希中查找它们的匹配数字是否在那里。 创buildmatrix是O(N * N),而在哈希中查找是恒定的时间。

将另一个数组D中所有对(i,j)的A [i] * B [j]存储在散列数据结构中。 这一步的复杂性是O(N * N)。

 construct a hash named D for i = 1 to n for j = 1 to n insert A[i]*B[j] into D 

2.对于C中的每个C [i],找出D中是否存在MC [i]。这一步的复杂度是O(N)。

 for i = 1 to n check if M - C[i] is in D 

我有一个解决scheme。 将列表中的所有元素插入到一个哈希表中。 这不会花费O(n)的时间。

一旦完成,你可以从剩余的2个数组中find所有的对,看它们的和是否存在于哈希表中。

因为散列连接是不变的,我们总共得到一个二次时间。

使用这种方法可以节省sorting时间。

另一个想法是,如果你知道每个元素的最大尺寸,你可以使用一个变化的桶sorting,并在nlogn时间。

以O(N ^ 2)空间为代价,但仍然使用O(N ^ 2)时间,可以通过计算前两个数组中所有可能的和,以及最后两个数组中所有可能的残基列表(可能是线性时间,因为它们都是'long'types,其位数与N无关),然后查看是否有任何和等于任何余数。

sorting所有3个数组,并使用二进制search似乎是一个更好的方法。 一旦数组sorting后,一定要进行二分search,而不是线性search,这取n而不是log(n)。

哈希表也是一个可行的select。

散列和sorting的组合可以减less时间,但是以O(N square)空间为代价。

我有另外的O(N^2)时间复杂度, O(N)额外的空间复杂性解决scheme。

首先,sorting三个数组,这一步是O(N*log(N)) 。 然后,对于A每个元素,创build两个数组V = Ai + BW = Ai + CAi是当前元素)。 Ai + B意味着这个新数组V中的每个元素都是B中的那个位置上的元素加AiA的当前元素)。 W = Ai + C是相似的。

现在,合并VW ,如合并sorting。 由于两者都是sorting的,所以这是O(N) 。 在这个有2*N元素的新arrays中,searchM + Ai (因为Ai被使用了两次)。 这可以用二进制search在O(log n)完成。

所以总的复杂度是O(N^2)

对三个数组进行sorting。然后初始化三个索引

  1. 我指着A的第一个元素,
  2. j指向B和B的最后一个元素
  3. k指向C的第一个元素。而i,j,k在它们各自的数组A,B,C的范围内

  4. 如果A [i] + B [j] + C [k] == M返回

  5. 如果A [i] + B [j] + C [k] <M,则如果A [i] <= C [k],则增加i,否则增加k。

  6. 如果A [i] + B [j] + C [k]> M,则减lessj。

哪个应该在O(n)中运行。

怎么样:

 for a in A for b in B hash a*b for c in C if Kc is in hash print abc 

这个想法是在A和B中散列所有可能的对。接下来,对于C中的每个元素,看看散列中是否存在剩余的zum。