python - 如何排列元组列表，以便删除与其他元组相比具有最高值的元组并返回最大值

Question

val = [(200, []), (300, [500, 200]), (400, [100, 200, 300]), (400, [])]
largest_val_arrangement(val)
[(200, []), (300, [500, 200]), (400, [100, 200, 300])]

所以现在 (400, []) 被弹出了，因为 (400, [100, 200, 300]) 的元素比它多。

Answer 1

您可以根据列表的长度使用排序，并使用字典，以便最后写入的键“获胜”。

然后转换回元组或列表或...保留为dict:

val = [(200, []), (300, [500, 200]), (400, [100, 200, 300]), (400, [])]

def largest_val_arrangement(val):
    return tuple({k:v for k,v in sorted(val, key = lambda t : len(t[1]))}.items())

largest_val_arrangement(val)

结果:

((200, []), (400, [100, 200, 300]), (300, [500, 200]))

这个方法，就像它使用的sort一样，有O(log(n)*n)的复杂度，(dict有O(1) 平均复杂度)。

但单线并不总是最有效的解决方案。这里使用 sort 是不必要的，当一个带有标记字典的旧循环在 O(n) 中工作时:

def largest_val_arrangement(val):
    d = dict()
    for k,v in val:
        if k not in d or len(d[k]) < len(v):
            d[k] = v

    return tuple(d.items())