Удалить определенный процент элементов из списка, сохраняя при этом структурную целостность списка - PullRequest
Новая
       49

Удалить определенный процент элементов из списка, сохраняя при этом структурную целостность списка

0 голосов
/ 23 сентября 2019

У меня есть список кортежей, где каждый кортеж содержит значение и объект, как показано ниже: 

[(1, object0), (1, object1), (0, object2), (5, object3)]

Теперь я должен был удалить 25% кортежей с самым низким значением в пределахПервая запись, в этом списке, я получу: 

[(1, object0), (1, object1), (5, object3)]

Здесь структурная целостность списка остается неизменной, в то время как элементы были удалены.Я исследовал варианты с приоритетной очередью, но я хотел знать, есть ли более эффективный способ сделать это.Пожалуйста, опишите временную сложность решения.

Я должен уточнить, что я ищу 25% нижних по значению списка из предыдущего примера.Если бы список сортировался по возрастанию, я бы получил: 

[(0, object2), (1, object0), (1, object1), (5, object3)]

Самый низкий 25% теперь будет первым элементом, но при выводе я сохраняю структурную целостность исходного списка.Порядок результата не имеет значения, если он не содержит нижних 25% по значению исходного списка.

Возможное решение

Возможное решение, которое, как я считаю, будет работатьиспользует очередь с минимальным приоритетом, которая содержит кортежи и добавляется в нее из списка.Тем не менее, они также добавляются в двусвязный список одновременно.Когда все элементы были добавлены в очередь и дважды связанный список, первый определенный процент элементов извлекается из очереди, а затем удаляется из связанного списка.Связанный список после всех удалений становится окончательным ответом.

1 Ответ

0 голосов
/ 23 сентября 2019 
ls = [(1, 'object0'), (1, 'object1'), (0, 'object2'), (5, 'object3')]
p25 = m.ceil(len(ls)/4)
ls25 = []
res  = []
for i,j in ls:
    if len(ls25)<p25:
        ls25.append(i)
    elif i < max(ls25):
        ls25.remove(max(ls25))
        res.append((i,j))
        ls25.append(i)
    else:
        res.append((i,j))
print(res)




output
[(1, 'object1'), (1, 'object2'), (5, 'object3')]
...