Как упорядочить список кортежей так, чтобы кортеж, связанный с самым высоким значением по сравнению с другим кортежем, удалялся и возвращал максимальный

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

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])]

Answer 2

Другой вариант, используя словарь по умолчанию из коллекций:

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])]

Answer 3

вы можете использовать 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 не нужно, когда старый добрый цикл с маркером dict работает в 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())