6

鉴于以下问题，我将不胜感激任何更正，因为我没有解决当前问题（取自我教授的考试之一！！！）：

备注：这不是作业！

问题：

给定两个排序数组A（带有长度n）和B（带有长度m），其中每个

元素（在两个数组中）是一个实数和一个数字X（也是一个实数），

我们想知道是否存在a ∈ Aand b ∈ B，例如：

a + b = X ，在O(n+m)运行时间。

解决方案 ：

首先，我们从两个数组的末尾开始检查，因为我们不需要大于 的数字X：

  • 我 = n

  • k = 米

  • 而 A[i] > X , i = i -1

  • 而 B[k] > X , k = k -1

定义 j = 0 。现在从当前i的 inA和jin开始运行B：

  • while i > 0 , j < k ：
  • if A[i]+B[j] == X，然后返回两个单元格
  • 别的j = j+1 , i = i -1

最后我们要么有这两个元素，要么我们会在一个或两个数组中超出界限，这意味着a + b = X确实不存在这样的两个元素。

任何评论将不胜感激

谢谢

4

3 回答 3

12

你不应该同时调整i和j。如果总和太大，你应该减少i。如果太小，请增加j。

于 2012-06-27T14:32:32.580 回答
4

这个问题是以下问题的特例： Find number in sorted matrix (Rows n Columns) in O(log n)

考虑一个用 填充的矩阵C[i,j] = A[i] + B[j]，然后从其中一个角开始，i如果总和太大，则减少，如果太小，则增加j。当然，您不必C在程序中创建和/或填充此矩阵，只需假设您知道此矩阵的任何元素：它是A[i] + B[j]，您可以随时立即计算它。得到的算法是O(m+n)。

于 2012-06-27T14:35:09.830 回答
1

我对家庭作业有同样的问题。在上网查之前我已经练过了。这是我的解决方案（Python），希望一些大佬看到并帮助我改进它

# 1.3. Given two sorted arrays a and b and number S. Find two elements such that sum a[i] + b[j] = S.Time O(n).

def find_elem_sum(alist, blist, S): # O(n)

if alist is None or alist == [] or blist is None or blist == []:
    return None

# find the numbers which are less than S in the lists
#
#
# pretend it is done

a_length = len(alist)
b_length = len(blist)
a_index, b_index = 0, 0
count = 0
while alist and a_index < a_length and b_index < b_length:
    count += 1
    if alist[a_index] + blist[b_index] < S:
        if a_index < a_length - 1:
            a_index += 1
        if a_index == a_length - 1:
            b_index += 1;
        continue
    elif alist[a_index] + blist[b_index] > S:
        alist = alist[:a_index]
        a_length = len(alist)
        a_index = a_length - 1
    elif alist[a_index] + blist[b_index] == S:
        return [a_index, b_index, count]

return None
于 2018-09-15T21:49:39.783 回答