python - 列表中的整数

Question

我需要从列表中获取相同的整数：正数和负数，例如，如果列表由 [0,1,-1,3] 组成，它只会返回 1 -1。到目前为止我有。

s = []
for i in a:
    if i in s
        s.append(i and -i)
print s

Answer 1

让我们直接把它从英语翻译成 Python。

首先，我们必须得到准确的英文描述：你想要所有在 中的值a，其否定也在 中a。

在 Python 中，这是：

[value for value in a if -value in a]

---

但是，如果您有一百万个值，-value in a则必须为每个值平均搜索 50 万个值，这意味着总比较次数为 50 万亿。你的一个同学显然把它上交了，并且因为在一些示例数据上花费了超过一分钟而本应该花费一秒钟的时间而受到指责。

您可以使用set. 在集合中查找一个值只需进行一次哈希查找和一次比较，而不必与每个值进行比较。所以：

s = set(a)
[value for value in a if -value in s]

---

有多种方法可以进一步优化。最明显的是，如果您不需要保留重复项或按顺序返回值，则可以只遍历集合而不是原始列表。但还有其他聪明的想法。你可以在这里看到一堆，以及一些比较。

Answer 2

要仅获取具有正数和负数对应部分的数字对，您可以使用如下列表推导：

>>> a = [0, 1, -1, 3]
>>> 
>>> [val for val in a if -val in a]
[0, 1, -1]

请注意，您还将0按预期获得 。如果您不希望这样做，也请添加一个明确的检查。

Answer 3

循环解决方案：

s = []
for i in a:
    if -i in a:
        s.append(i)

print s

过滤解决方案：

s = filter(lambda x: -x in s, s)

列表理解解决方案：

[x for x in s if -x in s]

仔细查看您的解决方案。如果您尝试同时附加 -i 和 i，您将添加重复值。此外，正如@kindall 提到的，您应该在两个 for 循环中使用 list a 。

这是解决方案的性能基准：

这是解决方案的性能基准：

我必须说 for 循环让我感到惊讶......

PS：答案适用于 python 2.7。在 python 3 中，地图、过滤器等是放置的，您必须使用类似 list(filter(lambda x: -x in s, s)) 的东西来评估它们。

Answer 4

我还没有看到索引是如何实现的，但很可能这是一个 O(n^2) 解决方案。

#!/usr/bin/env python

l = [ 1, 2 , -1 , 3]

for i in l:
    try:
        k = l.index(-1 * i )
        print i
    except ValueError as e:
        pass

更好的方法如下：

1. 排序列表：nlogn
2. 然后对于列表中的每个元素，对当前元素的负数进行二分搜索。您可以为此运行一个 for 循环。如果你得到一个命中打印元素。这也将是 nlogn。

因此，您将在 nlogn 时间内完成所需的工作。