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

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

给定两个数组 A 和 B K .

对取O(NlogN)的两个数组进行排序。
接受指示 i 和 j 我 一个 和 j型 指向 乙 .
A[i] + B[j] 并将其与 千

• A[i] + B[j] == K 我们发现了 一对 A[i] 和 B[j]
• 如果 A[i] + B[j] < K 增加总和,所以增加 我
• 如果 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 ).

您可以用两个数组将其简化为类似的问题,这是一个比较有名的问题,并且有简单的O(n)解决方案(包括从两端迭代)。

1. 对所有数组排序。
2. A 从第一个数组开始。
3. 找出最后两个数组是否能给出数字 B C ,使 B + C = M - A

第2步和第3步相乘得到了O(n^2)的复杂度。

其他的解决方案已经比较好了,但这是我的O(n^2)时间和O(n)内存解决方案。

取所有对(a,b),a,b(时间复杂度O(n^2))。 对于每一对,检查hastable中是否存在M-(a+b)(每个查询需要复杂度O(1))。

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

下一步是创建前两行和的“矩阵”。然后在散列中查找它们的匹配号码是否存在。创建矩阵是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中是否存在M-C[i],此步骤的复杂度为O(N)。

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

我有办法。将列表之一中的所有元素插入哈希表。这不需要多少时间。

完成后,找到其余2个数组中的所有对,并查看它们的和是否存在于哈希表中。

因为散列连接是常数,所以我们得到的总时间是二次方的。

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

另一个想法是,如果您知道每个元素的最大大小,可以使用bucket sort的变体,并在nlogn时间内完成。

以O(N^2)空间为代价,但仍然使用O(N^2)时间,人们可以处理 四 数组,通过计算前两个数组的所有可能和,以及后两个数组的所有可能余数,对列表进行排序(在线性时间内是可能的,因为它们都是“long”类型,其位数独立于N),然后查看任何和是否等于任何余数。

对所有3个数组进行排序并使用二进制搜索似乎是一种更好的方法。一旦数组被排序,就应该进行二进制搜索,而不是线性搜索,这需要n而不是log(n)。

哈希表也是一个可行的选择。

hash和sort的结合可以减少时间,但代价是O(N平方)空间。

我还有一个 O(N^2) 时间复杂性, O(N)

首先,对三个数组进行排序,这一步是 O(N*log(N)) . 那么,对于 A ,创建两个数组 V = Ai + B W = Ai + C ( Ai Ai + B 意味着这个新数组的每个元素 V 在那个位置的元素 B 加 艾岛 一个 ). W=Ai+C

现在,合并 五 W ,如合并排序。既然两个都分类了,这是 O(N) 2*N 元素,搜索 M + Ai 艾岛 使用两次)。这可以在 O(log n)

因此,总的复杂性是 O(N^2) .

1. 我指的是A的第一个元素,
2. j指向B的最后一个元素

3. 当i,j,k在它们各自的数组A,B,C的范围内时

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

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

它应该在O(n)中运行。

怎么样:

for a in A
 for b in B
  hash a*b

for c in C
 if K-c is in hash
   print a b c