Python删除元素列表中位置相同值的元素

Question

假设我有一个列表，其结构如下，包含大约 100 万个元素：

a = [["a","a"],["b","a"],["c","a"],["d","a"],["a","a"],["a","a"]]

删除a索引 0 处具有相同值的所有元素的最快方法是什么？结果应该是

b = [["a","a"],["b","a"],["c","a"],["d","a"]]

有没有比这更快的方法：

processed = []
no_duplicates = []

for elem in a:
    if elem[0] not in processed:
        no_duplicates.append(elem)
        processed.append(elem[0])

这可行，但附加操作需要很长时间。

Answer 1

您可以使用set保留第一个元素的记录并检查每个子列表的第一个元素是否在此。与 O(n) 时间相比，搜索解决方案需要 O(1) 时间。

>>> a = [["a","a"],["b","a"],["c","a"],["d","a"],["a","a"],["a","a"]]
>>> 
>>> seen = set()
>>> new_a = []
>>> for i in a:
...     if i[0] not in seen:
...             new_a.append(i)
...             seen.add(i[0])
... 
>>> new_a
[['a', 'a'], ['b', 'a'], ['c', 'a'], ['d', 'a']]
>>> 

空间复杂度：O(N) 时间复杂度：O(N) 搜索第一个元素是否存在：O(1)

如果没有要声明的新列表，则使用delelement，但这会增加时间复杂度