ama*_*loy 12 arrays algorithm search
我的一个朋友最近得到了这个面试问题,这在我们看来是可以解决的,但不是在面试官认为应该可能的渐近时间范围内.这是问题所在:
你有一个
N整数数组xs,排序但可能不同.您的目标是找到四个数组索引(1)(a,b,c,d),以便以下两个属性成立:Run Code Online (Sandbox Code Playgroud)xs[a] + xs[b] + xs[c] = xs[d] a < b < c < d目标是在O(N 2)时间内完成此操作.
首先,O(N 3 log(N))解决方案是显而易见的:对于每个(a,b,c)有序三元组,使用二进制搜索来查看是否d可以找到合适的.现在,如何做得更好？
面试官的一个有趣建议是将第一个条件重写为:
xs[a] + xs[b] = xs[d] - xs[c]
在此之后还不清楚该怎么做,但也许我们可以选择一些枢轴值P,并搜索一(a,b)对加起来为P,一(d,c)对减去它.对于给定的P,通过从数组的两端向内搜索,该搜索很容易在O(n)时间内完成.然而,在我看来,这个问题是N 2这样的值P,而不仅仅是N,所以我们实际上根本没有减小问题的大小:我们正在进行O(N)工作, O(N 2)次.
我们发现在其他地方在线讨论了一些相关的问题:在N 2时间内,在一个数组中找到添加到给定总和的3个数字是可解的,但要求总和提前修复; 适应相同的算法,但迭代每个可能的总和使我们一如既往地在N 3.
另一个相关的问题似乎是在数组中查找所有三元组,其总和小于或等于给定的总和,但我不确定这里有多少相关的东西:不等式而不是平等混合了很多东西,当然,目标是固定的而不是变化的.
那么,我们缺少什么？考虑到性能要求,问题毕竟是不可能的吗？还是有一个我们无法发现的聪明算法？
(1)实际上提出的问题是找到所有这样的(a,b,c,d)元组,并返回有多少元组的计数.但我认为即使在所需的时间限制内找到其中一个也很难.
如果算法必须列出解（即满足条件的a、b、c和d的集合），则最坏情况时间复杂度为O(n 4 )：
\n\n这个简单的例子是一个只有 0 个值的数组。那么a、b、c和d只要保持顺序就拥有所有自由。这表示O(n 4 )解。
\n\n但更一般地，遵循以下模式的数组具有O(n 4 )解：
\n\nw, w, w, ... x, x, x, ..., y, y, y, ... z, z, z, ....\n每种情况出现的次数一样多，并且：
\n\nw + x + y = z\n然而，只产生数量，算法可以具有更好的时间复杂度。
\n\n这是已经发布的算法的一个细微变化，它不涉及H因子。它还描述了如何处理不同配置导致相同总和的情况。
\n\n检索所有对并将它们存储在数组X中中，其中每个元素获取以下信息：
\n\na : 两者中最小的索引
\n b : 另一个索引
\n sum : 的值xs[a] + xs[b]
同时还将每个这样的对存储在另一个数组Y中中，如下所示：
\n\nc : 两者中最小的索引
\n d : 另一个索引
\n sum : 的值xs[d] - xs[c]
上述操作的时间复杂度为O(n\xc2\xb2)
\n\n[编辑：我无法证明O(n\xc2\xb2)的早期主张（除非做出一些假设允许基数/桶排序算法，我不会假设）。如评论中所述，通常具有n\xc2\xb2元素的数组可以按O(n\xc2\xb2logn\xc2\xb2)排序，即O(n\xc2\xb2logn)，但不是O(n\ xc2\xb2) ]
\n\n“串联”遍历两个数组以找到相等的和对。如果是这样的话，需要检查一下X[i].b < Y[j].c。如果是这样，它代表一个解决方案。但它们可能有很多，并且在可接受的时间内计算这些数量需要特别小心。
让，即数组Xm = n(n-1)/2中的元素数量（也是数组Y的大小）：
w, w, w, ... x, x, x, ..., y, y, y, ... z, z, z, ....\n请注意，尽管存在嵌套循环，但变量i只会递增，j也是如此。变量k在最内层循环中始终递减。尽管它也可以从更高的值开始，但它永远不能通过k索引对同一Y元素进行超过恒定次数的寻址，因为在递减该索引时，它保持在Y的“相同总和”范围内。
\n\n因此，这意味着算法的最后一部分运行时间为O(m)，即O(n\xc2\xb2)。正如我最新的编辑确认排序步骤不是O(n\xc2\xb2)，该步骤决定了总体时间复杂度：O(n\xc2\xb2logn)。
\n