逐项比较两个列表

Question

我有两个列表，想要逐项比较这些列表。 例如：

a = [1,2,3]
b = [2,3,1]
for i in a:
    if i in b:
        pass # do something
    else:
        pass # do something else instead

我觉得这个实现有点简单。

我想知道其他有效完成任务的方法。
(有效性意味着时间复杂度或空间复杂度)

- Kshitij Saraogi

Answer 1

您可以使用集合来查找a和b的共同元素。

common_elements = set(a) & set(b)
for item in a:
    if item in common_elements:
        pass # do something 
    else: 
        pass # do something else instead

在平均情况下，集合的构建复杂度为O(N)，集合成员测试复杂度为O(1)，因此整个算法的复杂度为O(N)。相比之下，列表成员测试的复杂度为O(N)，因此原始算法的复杂度为O(N^2)。

- Kevin

---

谢谢。我很感激你的解决方案，但我不能将列表转换为集合。我只能使用列表。 - Kshitij Saraogi

@KshitijSaraogi：为什么你不能使用集合？你使用的是非常老的Python版本吗？如果你不能使用集合，那么你只能使用O(n^2)算法...除非你实现自己的哈希表，但这会比使用Python集合慢得多，因为它在Python速度下运行，而不是在C速度下运行。 - PM 2Ring

@PM2Ring 我正在处理一些对象的列表，并且我想在其他几个地方使用这些列表。此外，我个人不喜欢为操作进行类型转换。 - Kshitij Saraogi

只是为了明确，列表并没有被“转换”成集合，也就是说a和b仍然是列表。创建common_elements对a和b没有影响；在执行该行代码之前，它们的类型和内容与之前相同。 - Kevin

@Kevin 谢谢你的建议。 - Kshitij Saraogi

Answer 2

我们可以使用一个临时数组来检查每个元素是否存在于b中。这个数组的大小应该大于两个列表中可能出现的最大元素（我在谷歌上搜索到32位系统中Python列表的最大大小为536,870,912，所以这种方法在正常情况下可行）。这个临时列表temp_b最初的每个元素都等于零。现在，对于列表b中存在的所有整数，我们将初始化该索引处的值为1，表示该元素存在于b中。之后，我们只需要对于a中的每个元素i，检查temp_b[i] == 1是否成立？如果是，则该元素存在，否则不存在。

请注意，要检查a中每个元素的频率是否也匹配b中的频率，我们必须修改此代码。复杂度将与数组的大小成线性关系。

a = [2, 5, 4, 7, 6, 8, 9]
b = [1, 3, 6, 7, 4, 3, 0]

temp_b = [0]*20

for i in b:
    temp_b[i] = 1

#to check whether each element of a is present in b or not
for i in a:
    if temp_b[i] == 1:
        #element is present
        print "present"
    else:
        #element is not present
        print "not present"

编辑：此方法仅适用于正整数。

- Shubham

---

如果 a 是 [1,2,3,4]，而且 b 是 [1,2,3] 呢？这不会导致 IndexError 吗？如果 a 是 [1,2,3,4] 而 b 是 [0,1,2,3] 呢？这不会说没有匹配，但实际上有三个吗？ - Kevin

是的，你说得对，也许我只是根据给定的值来判断你的问题。 - Shubham

Answer 3

a, b = [1, 2, 3], [2, 3, 1]
for i in map(lambda i:i in b,a):
    if i == True:
        # do someting
    else:
        # do other

- Ketul Patel

---

你应该尝试解释你的解决方案，而不仅仅是发布代码。 - samlev

@Ketul 如果您能解释一下您的答案，那将非常有帮助。 - Kshitij Saraogi

这段代码无法让你访问在b中的a当前元素，因此它的实用性极为有限。稍微好一点的方法是 for v, flag in map(lambda i:(i, i in b), a): if flag: #do stuff with v 等等。 - PM 2Ring