algorithm - 给定 3个排序数组A,B,C 和数字S,找到i,j,这样一个 [i] + B [j] + C [k] = S

  显示原文与译文双语对照的内容
0 0

我刚刚发现了如何在 O(n^2 log n) 时间( 假定每个 array的长度相同) 中解决这个问题:

for each A[i]:
 for each B[j]:
 if A[i] + B[j] + C.binarySearch(S - A[i] - B[j]) == S:
 return (i, j, k)

O(n^2) 时间内有什么方法可以解决这个问题,或者改进上述算法?

时间:原作者:7个回答

0 0

如果数组是非负
* 你可以将所有 3个数组修剪到S => A[n]> S
* 类似,如果 [aIdx] + B [bIdx]> S,则不要检查 array C

原作者:
0 0

准备:

  • 对每个 array 升序 +O(N.log(n)) 排序
  • 在每个 array ?O(log(N)) 上实现二进制搜索

计算机:

i=bin_search(smallest i that A[i]+B[0]+C[0]>=S); for (;i<Na;i++) { if (A[i]+B[0]+C[0]>S) break;
 j=bin_search(smallest j that A[i]+B[j]+C[0]>=S); for (;j<Nb;j++) { if (A[i]+B[j]+C[0]>S) break;
 ss=S-A[i]-B[j];
 if (ss<0) break;
 k=bin_search(ss);
 if (k found) return;//found solution is: i,j,k
 }
 }

如果我看到它是正确的, N=max(Na,Nb,Nc)M=max(valid intervals A,B,C)M<=N

  • (3*N.log(N)+log(N)+M*log(N)*M*log(N)) -> O((M^2)*log(N))
  • 可以只调用一次j 二进制搜索,如果需要,则迭代 +1
  • 的复杂性是相同的,但是N 改变了
  • 对于平均条件,这要快得多,因为 M<<N
原作者:
0 0

你的算法并不糟糕。 相对 n^2log(n) 增长得非常缓慢,实际上它可以被视为常量。 例如对于 n = 1000000n^2 = 1000000000000log(n) = 20 。 一旦 n 变得足够大,对 log(n) 有任何重要影响,n^2 就不能计算结果了。

一个解决方案,由 @YvesDaoust, 启发,但我不确定它是否完全相同:

  • 对于每个 A[i],计算余数 R = S - A[i] 它应该是一些 B[j]C[k]的组合;
  • 允许 j = 0k = |C|-1 ( C 中的最后一个索引) ;
  • if B[j] + C[k] <R 增加 j
  • if B[j] + C[k]> R 减少 k
  • 重复前面的两个步骤直到 B[j] + C[k] = R 或者 j> = |B| 或者 k <0

我建议不要用微优化太复杂的算法。 任何合理的数字集合都会足够快。 如果这些数组对于这种方法来说太大了,你的问题就会有很好的机器学习方法。

原作者:
0 0

O(N²) 解决方案非常简单。

首先考虑两个数组的情况,查找 A[i] + B[j] = S'

这可以重写为 A[i] = S' - B[j] = B'[j] :你需要在两个已经排序的数组中找到相等的值。 这很容易在线性时间内进行合并过程。 ( 你可以显式计算 array B',但这是不必要的,只需即时执行: 获取 S'- B[NB-1-j] 而不是获取 B'[j] ) 。

已经经建立了这个程序,它可以以用于 C的所有元素,在搜索 S - C[k] 时。

这里是 python 代码,并报告所有的解决方案。 ( 它被重写为 compact 和对称。)

for k in range(NC):
 # Find S - C[k] in top-to-tail merged A and B
 i, j= 0, NB - 1
 while i <NA and 0 <= j:
 if A[i] + B[j] + C[k] <S:
 # Move forward A
 i+= 1
 elif A[i] + B[j] + C[k]> S:
 # Move back B
 j-= 1
 else:
 # Found
 print A[i] + B[j] + C[k],"=", A[i],"+", B[j],"+", C[k]
 i+= 1; j-= 1

执行方式

A= [1, 2, 3, 4, 5, 6, 7]; NA= len(A)
B= [2, 3, 5, 7, 11]; NB= len(B)
C= [1, 1, 2, 3, 5, 7]; NC= len(C)
S= 15

15 = 3 + 11 + 1
15 = 7 + 7 + 1
15 = 3 + 11 + 1
15 = 7 + 7 + 1
15 = 2 + 11 + 2
15 = 6 + 7 + 2
15 = 1 + 11 + 3
15 = 5 + 7 + 3
15 = 7 + 5 + 3
15 = 3 + 7 + 5
15 = 5 + 5 + 5
15 = 7 + 3 + 5
15 = 1 + 7 + 7
15 = 3 + 5 + 7
15 = 5 + 3 + 7
15 = 6 + 2 + 7
原作者:
...