Python 具有多个列表和 if else 条件的列表理解

Python list comprehension with multiple lists and an if else conditon

我想遍历两个同样长的集合并确定每个集合中的元素是否也在一个数组中。

这是一个我已经解决的 Hackerrank 问题。但是,我正在使用 Hackerrank 来进一步了解 Python。我一直在学习列表理解,虽然我确实相信我是如何尝试使用它来被认为是糟糕的生产代码,但我仍然想根据自己的知识探索语言语法的可能性。

这是设置它的代码:

n, m = map(int, input().split())
arr = list(map(int, input().split()))
A = set(map(int, input().split()))
B = set(map(int, input().split()))

任务是为 A 和 arr 中的每个元素输出一个值为 +1 的整数,为 B 和 arr 中的每个元素输出一个值为 -1 的整数。

示例输入:

3 2
1 5 3
3 1
5 7

示例输出:

1

这达到了要求的结果:

print(sum([1 for a in A if a in arr]) + sum([-1 for b in B if b in arr]))

然而,这更接近我想要实现的目标:

sum([1 if a in arr else -1 if b in arr for a, b in zip(A, B)])

编辑(实际上更接近):

print(sum(1 if a in arr -1 if b in arr for a, b in zip(A, B)))

如您所见,两者都是单行代码,因此这并不是要尝试减少代码,而是要了解列表理解和 pythonic 代码的可能性。如果这是不可能的,甚至是不好的做法,我也很感兴趣。

这是 Hackerrank link: https://www.hackerrank.com/challenges/no-idea

首先,放弃列表理解;使用生成器表达式将值直接输入 sum()

sum(1 for a in A if a in arr)

如果A是一个集合,用set.intersection() method提取公共值,然后取结果长度:

len(A.intersection(arr)))

这比尝试为每个值测试 arr 更快。 确实首先生成了一个新的set()对象,但是你之前创建了一个列表,所以这没什么区别。

到那时,简单得多,只需减去第二个长度:

len(A.intersection(arr)) - len(B.intersection(arr))

您可以通过循环 arr 并针对 AB 测试 arr 中的每个值来完全避免创建集合;这也更快,因为集合成员测试是 O(1) 常数时间:

sum(1 if v in A else -1 if v in B else 0 for v in arr)

你的方法是为集合 A 中的每个值测试 a in arr,如果值 a 不存在,则需要对 arr 进行完整列表扫描;这使得针对列表的成员资格测试成为 O(N) 线性时间问题,并且您对 A 中的每个值 B 中的每个值都这样做,所以你最终得到 O((A+B) * N) == O(KN) 时间。针对集合测试 arr 中的每个值仅需 O(N * 1) == O(N) 时间。

此外,如果 arr 中的值不是唯一的,您的方法实际上会导致错误的答案;你只会计算快乐或不快乐的数字一次,而这个问题要求它们每次出现时都要计算一次。

数组转换成集合取交如何

s = set(arr)
print(len(A.intersection(s)) - len(B.intersection(s)))

编辑: 此解决方案不适用于 arr

中的重复值

您的解决方案很棒,但有一个问题。您正在为两组数字使用 set 数据结构,为数组使用 list 。在列表顶部应用 in 运算符时,您正在进行 O(n) 搜索,而在集合中,相同的操作是 O(logn) (在 python 中,平均情况是 O(1)! ).所以你的总时间复杂度是 O(2 * m * n) = O(m*n)。您可以反向搜索,例如:

For each element in array, if element in A then +1, if element in B then -1.

总复杂度为 O(n * 2 * logm) = O(n*logm)

有关 python 时间复杂度的更多信息 here

这是我提交的答案,因为我最初想到的是使用列表推导式。这是唯一必要的,因为数组可能有多个相同元素,因此计数需要反映这一点。

n, m = map(int, input().split())
arr = list(input().split())
A, B = set(input().split()), set(input().split())
print(sum([(e in A) - (e in B) for e in arr]))

解决问题最有效的方法可能是将AB的项目放入字典(作为键),值为1-1 取决于他们来自哪个集合。这将使您扫描列表 arr 并轻松获得要添加到总和的值:

ab_dict = {a: 1 for a in A}
ab_dict.update((b, -1) for b in B)

result = sum(ab_dict.get(x, 0) for x in arr)

结果的计算与在生成器表达式中使用几个条件运算符 (sum(1 if x in A else -1 if x in b else 0 for x in arr)) 具有相同的计算复杂度,但应该更快一些常数因子,因为对于每个项目只有一个 dict 查找而不是两个集合成员资格测试。