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])
更少元素。
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])
更少元素。
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())
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])]
另一种选择是使用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])]
O(n)
,所以更好。吹毛求疵:使用defaultdict(list)
代替lambda:[]
。当我找到你的解决方案时,我回来添加了一个类似的答案(使用标准字典而不是默认字典)。 - Jean-François Fabre