如何基于嵌套列表的单列提取唯一子列表？

给定嵌套列表，需要提取每个首元素第一次出现对应的子列表，示例如下：

in_list = [['a','b'], ['a','d'], ['e','f'], ['g','h'], ['e','i']]
out_list = [['a','b'], ['e','f'], ['g','h']]

你当前的实现是拆分两个列表逐个检查，代码如下：

lis = [['a','b'], ['a','d'], ['e','f'], ['g','h']]
lisa = []
lisb = []
for i in lis:
    if i[0] not in lisa:
        lisa.append(i[0])
        lisb.append(i[1])
out = []
for i in range(len(lisa)):
    temp = [lisa[i],lisb[i]]
    out.append(temp)

但处理百万级以上子列表时，i[0] not in lisa是线性查找，整体时间复杂度为O(n²)，性能会非常差。

优化方案：用字典实现O(n)时间复杂度 #

字典的键具有唯一性，且查找操作是O(1)时间复杂度，刚好适配需求：遍历列表时，只保留每个首元素第一次出现的子列表，最后提取字典的值即可。

代码实现（Python 3.7+） #

in_list = [['a','b'], ['a','d'], ['e','f'], ['g','h'], ['e','i']]
seen = {}
for item in in_list:
    key = item[0]
    if key not in seen:
        seen[key] = item
out_list = list(seen.values())
print(out_list)  # 输出: [['a','b'], ['e','f'], ['g','h']]

Python 3.7及以上版本的字典会保留插入顺序，所以结果的顺序和原列表中首次出现的顺序一致。

兼容低版本Python（3.6及以下） #

如果使用Python 3.6或更早版本，普通字典不保证顺序，可以用collections.OrderedDict来实现：

from collections import OrderedDict

in_list = [['a','b'], ['a','d'], ['e','f'], ['g','h'], ['e','i']]
seen = OrderedDict()
for item in in_list:
    key = item[0]
    if key not in seen:
        seen[key] = item
out_list = list(seen.values())

内容的提问来源于stack exchange，提问作者Anurag Shukla