删除相似性Python

Question

该列表包含其他列表:

L = [[3, 3], [4, 2], [3, 2]]

如果子列表的第一个元素等于其他子列表的第一个元素,则必须从整个列表中删除具有较高第二个元素的元素.

所以新的名单是:

L = [[4,2], [3,2]]

如何尽可能高效地完成这项工作？

Answer 1

L.sort(key=lambda x: x[1], reverse=True)
L = OrderedDict(L).items()

为什么这样有效

如果你dict(L)使用L列表或元组,这或多或少等同于:

{k: v for k, v in L}

如您所见,如果存在重复的键(k),则后面的值将覆盖先前的值.

如果我们能够L输入正确的订单,我们可以利用这一点.

在您的情况下,我们并不真正关心键的顺序,但我们希望稍后出现较低的值(即子列表的第二个元素).这样,任何较低的值都会使用相同的密钥覆盖较高的值.

按子列表的第二个元素排序(按相反顺序)就足够了.由于list.sort()稳定,这也尽可能保留条目的原始顺序.

L.sort(key=lambda x: x[1], reverse=True)

collections.OrderedDict(L) 现在通过第一个元素使元素唯一,保持插入顺序.

该sort()是O(n ln n)和字典创作又增加了O(n).没有这种情况可以做到:

d = OrderedDict()    
for k, v in L:    
    ev = d.get(k, None)    
    # update value. Always if key is not present or conditionally
    # if existing value is larger than current value
    d[k] = v if ev is None or ev > v else ev    

L = d.items()

但这是更多的代码,可能根本没有,或者在纯Python中没有那么快.

编辑:(1)使用非整数键(2)它足以按第二个元素排序,不需要完整排序.