如何检查 python 中两个列表之间的公共元素

Question

我在尝试检查列表中的重叠元素时遇到了一些麻烦。

这意味着我将不得不检查两个列表之间的共同元素。

我的程序的工作方式是玩家输入某艘船的两端坐标，然后根据所有船坐标创建一个列表（即如果他们输入 (1,1)和 (1,5)，它将创建 [(1,1),(1,2),(1,3),(1,4),(1,5)]

我也尝试过使用以下代码，但它无法按照我想要的方式工作：

ListA = [(1,1),(1,2),(1,3),(1,4),(1,5)]
ListB = [(1,1),(2,1),(3,1)]

    for i in ListB:
        if i in ListA:
            print("There is an overlap")
            #choose coordinates again
        else:
            print("There is no overlap")
            #add to ListA and next ship's coordinate chosen

我希望程序通过整体考虑来检查 A 中的任何元素是否在 B 中，而不是单独检查它们。

Answer 1

set.intersection 将查找任何共同元素：

ListA = [(1,1),(1,2),(1,3),(1,4),(1,5)]
ListB = [(1,1),(2,1),(3,1)]
print(set(ListA).intersection(ListB))
set([(1, 1)])

除非顺序很重要，否则最好将元组存储在集合中：

st_a = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5)}
st_b = {(1, 1), (2, 1), (3, 1)}
print(st.intersection(st_b))

将其添加到您的代码中：

if st_a.intersection(st_b):
     print("There is an overlap")            
else:
    print("There is no overlap")

Answer 2

如果有重叠你想重新选择坐标；

for i in ListB:
    if i in ListA:
        print("There is an overlap")
        i=(yourcoordinateshere)

否则您想将其添加到 ListA;

else:
    print("There is no overlap")
    ListA.append(i)

Answer 3

不确定这是否有帮助...

In [1]: from collections import Counter

In [2]: import random

In [3]: lst = [random.randrange(0, 9) for i in xrange(1000)]

In [4]: counted = Counter(lst)

In [7]: counted.most_common(10)
Out[7]: 
[(2, 125),
 (0, 123),
 (5, 120),
 (8, 118),
 (7, 111),
 (1, 107),
 (4, 104),
 (6, 102),
 (3, 90)]

Answer 4

词典

如果在实践中：

 len(ListA) * len(ListB) * ExpectedNumberOfCollisionChecks

很重要，那么对较长的列表使用字典可能有意义，因为字典查找的时间复杂度为：

平均：O(1)
最坏情况：O(n)

平均值是预期的，最坏的情况只有在选择了错误的哈希函数时才会发生。

相交集

已接受的答案建议使用 set.intersection。 time complexity of set.intersection 是：

平均：O(n)
最坏情况：O(n^2)

修改代码

对原始代码的唯一更改是将 ListA 转换为 MapA。

MapA = {(1,1): True, (1,2): True, (1,3): True,(1,4): True, (1,5): True}
ListB = [(1,1),(2,1),(3,1)]

for i in ListB:
    if MapA.get(i):
        print("There is an overlap")
        #choose coordinates again
    else:
        print("There is no overlap")
        #add to ListA and next ship's coordinate chosen

如何检查 python 中两个列表之间的公共元素

How to check for common elements between two lists in python

python

list

词典

相交集

修改代码

评论