以线性时间复杂度在两个列表中查找公共元素

Question

我有两个未排序的整数列表，没有重复项。它们都包含相同的元素，但顺序不同。我希望以最低的时间复杂度找到两个列表之间公共元素的索引。比如说

a = [1, 8, 5, 3, 4]
b = [5, 4, 1, 3, 8] 

输出应为：

list1[0] With list2[2]
list1[1] With list2[4]
list1[2] With list2[0]
and so on 

我曾想过使用set。交叉点，然后使用“index”函数查找索引，但我不知道如何以正确的方式打印输出

这就是我尝试过的

b = set(list1).intersection(list2)
ina = [list1.index(x) for x in b]
inb = [list2.index(x) for x in b]
print (ina , inb )

Answer 1

a = [1, 8, 5, 3, 4]
b = [5, 4, 1, 3, 8]

e2i = {e : i for (i, e) in enumerate(b)}
for i, e in enumerate(a):
    if e in e2i:
        print('list1[%d] with list2[%d]' % (i, e2i[e]))

Answer 2

要在线性时间内找到它们，应该使用某种散列。Python中最简单的方法是使用dict：

list1 = [1, 8, 5, 3, 4]
list2 = [5, 4, 1, 3, 8]

common = set(list1).intersection(list2)
dict2 = {e: i for i, e in enumerate(list2) if e in common}
result = [(i, dict2[e]) for i, e in enumerate(list1) if e in common]

result将是

[(0, 2), (1, 4), (2, 0), (3, 3), (4, 1)]

您可以使用类似这样的方式格式化和打印：

for i1, i2 in result:
    print(f"list1[{i1}] with list2[{i2}]")

你会得到：

list1[0] with list2[2]
list1[1] with list2[4]
list1[2] with list2[0]
list1[3] with list2[3]
list1[4] with list2[1]

Answer 3

创建一个字典，将一个列表的元素映射到它们的索引。然后更新它，使其具有另一个列表的相应元素的索引。然后，具有两个索引的任何元素都位于交点处

intersect = {x: [i] for i, x in enumerate(list1)}
for i, x in enumerate(list2):
    if x in intersect:
        intersect[x].append(i)
for l in intersect.values():
    if len(l) == 2:
        print(f'list1[{l[0]}] with list2[{l[1]}]')