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

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])更少元素。

- Haryo Dollybim

---

最终结果中的顺序重要吗？ - timgeb

no order does not matter. - Haryo Dollybim

Answer 1

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

然后将其转换回tuple或list或...保留为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())

- Jean-François Fabre

Answer 2

O(n)解法

>>> val = val = [(200, []), (300, [500, 200]), (400, [100, 200, 300]), (400, [])]
>>>
>>> seen = {}
>>> for k, lst in val:
...:    if len(lst) > len(seen.get(k, [])):
...:        seen[k] = lst
...:        
>>> list(seen.items())
[(200, []), (300, [500, 200]), (400, [100, 200, 300])]

- timgeb

---

对我们来说，这是一个很好的教训：在这种问题中，“sort”被高估了。 - Jean-François Fabre

@Jean-FrançoisFabre 是的，在Python 3.7中，字典解决方案甚至可以保留顺序。 - timgeb

Answer 3

另一种选择是使用collections中的默认字典：

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

from collections import defaultdict
tmp = defaultdict(list)

for x in val:
  if len(x[1]) > len(tmp[x[0]]): tmp[x[0]] = x[1]

res = [(k, v) for k,v in tmp.items()]
print(res)

#=> [(200, []), (300, [500, 200]), (400, [100, 200, 300])]

- iGian

---

那是O(n)，所以更好。吹毛求疵：使用defaultdict(list)代替lambda:[]。当我找到你的解决方案时，我回来添加了一个类似的答案（使用标准字典而不是默认字典）。 - Jean-François Fabre

谢谢你的提示@Jean-FrançoisFabre - iGian