Python Выберите лучший 4 из списка JSON

Question

У меня есть отсортированный список JSON, например:

[{ "id": "1", "score": "5" }, 
{ "id": "1", "score": "4" }, 
{ "id": "2", "score": "9" }, 
{ "id": "2", "score": "8" }, 
{ "id": "3", "score": "99" }, 
{ "id": "3", "score": "98" }] 

Это отсортированный по идентификатору, а также базы по идентификатору, оценка также отсортированы. Теперь я хочу выбрать лучшие 4 балла каждого идентификатора и сохранить их в новом списке. Идентификатор может иметь более 4 баллов, также может не иметь более 4 баллов. Время сортировки должно быть O (n), любая идея?

Answer 1

Поскольку уже отсортированы по рейтингу, просто перебрать его и получить лучшие четыре для каждого идентификатора, и вы сделали с O(n) временной сложностью.

Вот как:

import itertools 

new_lst = [] 
for _, g in itertools.groupby(lst, key=lambda x: x['id']): 
    new_lst.extend(sorted(g, key=lambda x: x['score'], reverse=True)[:4]) 

Не реальный тест:

>>> lst = [{ "id": "1", "score": "5" }, 
{ "id": "1", "score": "4" }, 
{ "id": "2", "score": "9" }, 
{ "id": "2", "score": "8" }, 
{ "id": "3", "score": "99" }, 
{ "id": "3", "score": "98" }] 
>>> new_lst = [] 
>>> for _, g in itertools.groupby(lst, key=lambda x: x['id']): 
    new_lst.extend(sorted(g, key=lambda x: x['score'], reverse=True)[:4]) 

>>> new_lst 
[{'id': '1', 'score': '5'}, {'id': '1', 'score': '4'}, {'id': '2', 'score': '9'}, {'id': '2', 'score': '8'}, {'id': '3', 'score': '99'}, {'id': '3', 'score': '98'}] 

Answer 2

отсортировать список по id и score который принимает 0(n) и группировать их по id атрибутом, который также принимает 0(n).

import itertools 

lst = sorted(lst, key=lambda x: (int(x['id']), int(x['score']))) 
grouped = itertools.groupby(lst, key=lambda x: x['id']) 

for x, y in grouped: 
    print list(y)[:-4]