两个数组和数字 - 最佳算法

Question

这是我在求职面试中遇到的一个问题:

您将获得两个排序的数组(大小为n和m),以及一个数字x.找到两个数字的索引(每个数组一个)的最佳算法是什么,它们的总和等于给定的数字.

我找不到比天真解决方案更好的答案:

1. 从较小的数组开始,从包含小于x的最大数字的单元格开始.
2. 对于小阵列中的每个单元格.对大的二进制搜索,寻找数字,使得总和等于x.
3. 继续,直到较小数组的第一个单元格,返回适当的索引.
4. 如果不存在这样的数字,则返回FALSE.

任何人都可以想到运行时更好的解决方案吗？

Answer 1

使用两个索引i1,i2- 设置i1=0, i2=n-1

while i1 < m && i2>=0:
    if arr1[i1] + arr2[i2] == SUM:
         return i1,i2
    else if arr1[i1] + arr2[i2] > SUM:
         i2--
    else
         i1++
return no pair found

我们的想法是使用数组排序的事实,因此从数组的两个边开始,并在每次迭代时进行更改,以便更接近所需的元素

复杂性是O(n+m)在最坏情况分析下,如果是,则优于二分搜索方法min{m,n} >= log(max{m,n})

正确性证明(指南):

假设答案是true指数k1,k2.
然后,每个i2>k2- arr1[k1] + arr2[i2] > SUM- i1在到达之前你不会改变它i2==k2.同样地,你可以证明,当你到达时i2==k2,你不会i2在到达之前改变i1==k1.
由于我们线性扫描数组 - 其中一个i1或i2将到达k1或k2在某个点,然后 - 您将继续迭代,直到您将另一个迭代器设置到正确的位置,并找到答案.
QED

注意:
如果要输出与所需总和匹配的所有元素,请将arr1[i1]+arr2[i2] ==SUM具有LOWER绝对差异的元素更改为迭代顺序中的下一个元素.它将确保您输出所有所需的对.

请注意,此解决方案可能因重复元素而失败.原样,如果没有对(x,y)使得x和y都具有欺骗,则解决方案有效.
要处理这种情况,一旦你在一个方向上耗尽了所有可能的对,你将需要'重新启动',并且伪代码应该更新为:

dupeJump = -1
while i1 < m && i2>=0:
    if arr1[i1] + arr2[i2] == SUM:
         yield i1,i2
         if arr1[i1+1] == arr1[i1] AND arr2[i2-1] == arr2[i2]:
             //remembering where we were in case of double dupes
             if (dupeJump == -1):
                 dupeJump = i2
             i2--
         else:
             if abs(arr1[i1+1] - arr1[i1]) < abs(arr2[i2-1] - arr2[i2]):
                 i1++
             else:
                 i2--
            //going back up, because there are more pairs to print due to dupes
             if (dupeJump != -1):
                 i2 = dupeJump 
                 dupeJump = -1
    else if arr1[i1] + arr2[i2] > SUM:
         i2--
    else
         i1++

但请注意,时间复杂度可能会增加O(n+m+size(output)),因为可能存在O(n*m)这样的对,并且您需要输出所有这些对(请注意,每个正确的解决方案都会有此限制).