在一定范围内寻找两个列表中的元素

Question

我有两张单子，L1是这样排列的：

L1 = ['12:55:35.87', '12:55:35.70', ...]
L2 = ['12:55:35.53', '12:55:35.30', ...]

我试图在两个列表中都找到以相同的4个字符开头的对，即。 xx:x，然后返回每个列表对的索引

到目前为止，我已经：

for pair1 in L1:
    for pair2 in L2:
        if pair1[:4] in pair2:
            print(L1.index(pair1))

这似乎没有返回正确的索引，而且显然也没有返回第二个列表的索引。任何帮助都将不胜感激。你知道吗

Answer 1

下面是如何让你的代码工作。请记住，这是一个幼稚的解决方案，有更快的方法来解决这个问题，如果你的名单是大的。这里的运行时间是O（n^2），但这可以在线性时间内解决。你知道吗

for i,pair1 in enumerate(L1):
    for j,pair2 in enumerate(L2):
        if pair1[:4] == pair2[:4]:
            print("list1: %s , list2: %s" % (i,j))

更新：对于未来的访问者，这里有一个平均线性时间解决方案：

from collections import defaultdict
l1_map = defaultdict([])

for i,val in enumerate(L1):
    prefix = val[:4]
    l1_map[prefix].append(i)


for j,val in enumerate(L2):
     prefix = val[:4]
     for l1 in l1_map[prefix]:
        print("list1: %s , list2: %s" % (l1,j))

Answer 2

可以使用^{}循环笛卡尔积。你知道吗

from itertools import product

L1 = ['12:55:35.87', '12:55:35.70']
L2 = ['12:55:35.53', '12:45:35.30']

res = [(i, j) for (i, x), (j, y) in 
       product(enumerate(L1), enumerate(L2)) 
       if x[:4] == y[:4]]

# [(0, 0), (1, 0)]

Answer 3

因为OP列表似乎有很多重复的“前四个字符”，我会做如下操作：

indices = {}
for i, entry in enumerate(L1):
    indices.setdefault(entry[:4], [])
    indices[entry[:4]].append("L1-{}".format(i))
    if L2[i][:4] in indices:
        indices[L2[i][:4]].append("L2-{}".format(i))

然后您可以通过以下方式访问重复的条目：

for key in indices:
    print(key, indices[key])

这比O（n^2）好。你知道吗

编辑：正如有人在评论中指出的，这是假设列表共享相同的长度。你知道吗

如果没有，则假设L2大于L1，然后在执行上述操作之后，可以执行以下操作：

for j, entry in enumerate(L2[i+1:]):
    indices.setdefault(entry[:4], [])
    indices[entry[:4]].append("L2-{}".format(j))

如果L2比L1短，只需更改所示代码中的变量名称。你知道吗