给定以下问题,如有纰漏请指正,因为我没有当前问题的解决方案(取自我的教授的考试!!!):
注意:这不是作业!
问题:
给定两个已排序数组A(长度为n)和B(长度为m),其中每个元素(在两个数组中)都是实数,以及一个数字X(也是实数),我们想知道是否存在a∈A和b∈B,使得:
a + b = X,在O(n+m)运行时间内。
解决方案:
首先,我们从两个数组的末尾开始检查,因为我们不需要比X更大的数字:
i = n k = m while A[i] > X,i = i - 1 while B[k] > X,k = k - 1
定义j = 0。 现在从A中的当前i和B中的j开始运行:
while i > 0,j < k: if A[i]+B[j] == X,则返回两个单元格 else j = j+1,i = i -1
最后,我们将拥有两个元素,或者我们将达到一个或两个数组的边界,这意味着确实不存在两个元素,例如a+b=X.
非常感谢您的任何评论。
注意:这不是作业!
问题:
给定两个已排序数组A(长度为n)和B(长度为m),其中每个元素(在两个数组中)都是实数,以及一个数字X(也是实数),我们想知道是否存在a∈A和b∈B,使得:
a + b = X,在O(n+m)运行时间内。
解决方案:
首先,我们从两个数组的末尾开始检查,因为我们不需要比X更大的数字:
i = n k = m while A[i] > X,i = i - 1 while B[k] > X,k = k - 1
定义j = 0。 现在从A中的当前i和B中的j开始运行:
while i > 0,j < k: if A[i]+B[j] == X,则返回两个单元格 else j = j+1,i = i -1
最后,我们将拥有两个元素,或者我们将达到一个或两个数组的边界,这意味着确实不存在两个元素,例如a+b=X.
非常感谢您的任何评论。