我将如何编写新算法，该算法使用 A 和 B 排序的事实来实现比这更好的运行时复杂性

Question

Algorithm bar(A,n,B,m)
  Input: arrays of integers, A of length n and B of length m
  Output: true or false
for i := 0 to n-1
    for j := 0 to m-1
        if A[i] == B[j]
            return true
        endif
    endfor
endfor
return false

Answer 1

您可以同时从头到尾遍历两个数组，在B或A上进行，具体取决于哪个元素较小(假设数组按升序排序(：

def bar(A, n, B, m):
    x = 0
    y = 0
    while x < n and y < m:
        if A[x] < B[y]:
            x++
        elif A[x] > B[y]:
            y++
        else:
            return True
    return False

最坏情况的运行时是O(n + m) - 遍历两个数组一次而没有找到匹配的对。