提取python列表中非重复元素的索引

Question

我有一个清单：

input = ['a','b','c','a','b','d','e','d','g','g']

我想要列表中除重复项之外的所有元素的索引。

output = [0,1,2,5,6,8]

Answer 1

您应该迭代枚举列表，并将每个元素添加到一组“已看到”元素中，如果该元素尚未被看到（不在“已看到”集合中），则将索引添加到输出列表中。

哦，这个名字input覆盖了内置input()函数，所以我重命名了它input_list。

output = []
seen = set()
for i,e in enumerate(input_list):
    if e not in seen:
        output.append(i)
        seen.add(e)

这给出output了[0, 1, 2, 5, 6, 8].

为什么要使用一套？

您可能会想，当您可以执行以下操作时为什么要使用集合：

[i for i,e in enumerate(input_list) if input_list.index(e) == i]

这是可行的，因为.index返回列表中具有该值的第一个元素的索引，因此如果您对照此检查元素的索引，您可以断言它是该元素的第一次出现并过滤掉那些不存在的元素这不是第一次出现。

但是，这不如使用集合那么有效，因为list.index需要 Python 迭代列表，直到找到元素（或找不到）。这个操作很O(n)复杂，因为我们为 中的每个元素调用它input_list，所以整个解决方案将是O(n^2)。

另一方面，像第一个解决方案一样使用集合会产生一个O(n)解决方案，因为检查元素是否是in集合很复杂O(1)（平均情况）。这是由于集合的实现方式所致（它们类似于列表，但每个元素都存储在其哈希的索引处，因此您只需计算元素的哈希并查看是否有一个元素可以检查成员资格，而不是迭代它 - 请注意，这是一个模糊的过度简化，但这是他们的想法）。

因此，由于每次成员​​资格检查都是O(1)，并且我们对每个元素都执行此操作，因此我们得到的O(n)解决方案比解决方案要好得多O(n^2)。