python-3.x - 两个列表之间的最小差值对

Question

我有两个 list 整数。我需要从每个列表中找到一个绝对差异最小的元素。

执行时间为 1 秒，我的代码超出了允许的时间。如何优化它？

m = int(input())   #number of elements in list1
list1 = list(map(int, input().split()))
z = int(input())    #number of elements in list2
list2 = list(map(int, input().split()))
minDiference = abs(list1[0] - list2[0])
for i in range (m):
    for j in range(z):
        diference = abs(list1[i] - list2[j])
        if difference < mindifference:
            mindifference = difference
print(mindifference)

Answer 1

您当前的复杂度是 O(m*z)，您可以将其降低到 O(max(m*log(m), z*log(z)) 通过对列表进行排序!

l1 = sorted(list1)
l2 = sorted(list2)

i = j = 0

minimum = float('inf')

while i < m and j < z:
    diff = l1[i] - l2[j]
    minimum = min(minimum, abs(diff))
    if diff < 0: # Means the value of the current position is lower than the l2's, move the l1's pointer
        i += 1
    elif diff > 0: # Quite similar
        j += 1
    else:
        break

print(minimum)