如何高效筛选元组列表，保留首元素同分组中末元素最大的元组

你原来的代码采用了双重循环遍历所有元素配对，时间复杂度为O(n²)，当列表长度增长时运算量会呈平方级暴涨，运行慢是必然结果。优化思路可以采用字典按元组首元素分组，全程仅遍历一次列表，时间复杂度降到O(n)，性能提升非常明显，同时写法也更符合Python风格。

最优实现方案（推荐） #

sample_list = [(5,16,2),(5,10,3),(5,8,1),(21,24,1)]
res_dict = {}
for tup in sample_list:
    key = tup[0]
    # 同首元素的元组，仅保留末元素更大的那个
    if key not in res_dict or tup[-1] > res_dict[key][-1]:
        res_dict[key] = tup
op = list(res_dict.values())
print(op)

运行输出完全符合预期：[(5, 10, 3), (21, 24, 1)]。

注：Python3.7及以上版本字典默认保留插入顺序，输出结果的顺序和原列表中首元素首次出现的顺序一致。

函数式写法（可选） #

如果偏好函数式编程风格，也可以用itertools.groupby实现，时间复杂度为O(n log n)（需要先按首元素排序），性能略低于字典方案，但也远优于你原来的双重循环实现：

from itertools import groupby

sample_list = [(5,16,2),(5,10,3),(5,8,1),(21,24,1)]
op = []
for key, group in groupby(sorted(sample_list, key=lambda x:x[0]), key=lambda x:x[0]):
    # 每组取末元素最大的元组
    op.append(max(group, key=lambda x:x[-1]))
print(op)

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