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

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

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

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]}]')