利用单调性把O(N^2)变成O(N)

登录以参加训练计划

假定有两个集合A、B，从A里面找B在不在。 常规路数是

for a in A:
    found = False
    for b in B:
        if a == b:
            found = True
            break
    if found:
        print("a in B")
    else:
        print("a not in B")

双层循环，时间复杂度O(nm)

但如果我们把A B排序

A.sort()
B.sort()

a_idx = 0
b_idx = 0
while a_idx < n and b_idx < m:
    if A[a_idx] == B[b_idx]:
        print("a in B")
        a_idx += 1
    
    b_idx += 1

O(m)