从列表中删除重复元组,具体取决于元组中的值

Question

我有一个元组列表.每个元组包含2个元素:

• 第一个元素是一个带有一些数字的元组,例如(1,4,2).这实际上是一个路径,其中的数字是节点的ID.
• 第二个元素是一个数字,它是路径的分数.

例如,列表可能是

pathList = [
    ((1, 2),    4),
    ((1, 4, 2), 2),
    ((1, 2),    6),
    ((1, 2),    3),
    ((1, 4, 2), 3)
]

现在我想删除与其他路径具有相同路径(第一个元素)的元组,同时保留其中具有最高分数(第二个元素)的元组.

例如,经过这个过程,pathList应该是

pathList = [
    ((1, 2),    6),
    ((1, 4, 2), 3)
]

订单并不重要.

有没有一种有效的方法呢？

Answer 1

您可以使用字典(dict.setdefault方法)将路径保存为键和相对分数作为值(添加值的O(1)复杂度)值,然后选择每个唯一路径的最大分数:

>>> pathList = [
...     ((1, 2),    4),
...     ((1, 4, 2), 2),
...     ((1, 2),    6),
...     ((1, 2),    3),
...     ((1, 4, 2), 3)
... ]
>>> 
>>> d={}
>>> for i,j in pathList:
...   d.setdefault(i,set()).add(j)
... 
>>> [(i,max(j)) for i,j in d.items()]
[((1, 2), 6), ((1, 4, 2), 3)]