Очередь, из которой можно удалить первые вхождения
Я участвовал в соревновании по программированию на Amazon, и один из вопросов был очень простым. Перефразируя:
Разработайте метод обработки корзин покупок, который принимает два входных параметра:
itemsтекущая корзина покупок, представляющая собой массив идентификаторов продуктов, иqueueидентификаторы операций, которые нужно применить к корзине покупок.Если идентификатор положительный, добавьте идентификатор продукта в конец корзины, если идентификатор отрицательный, удалите первый экземпляр абсолютного значения идентификатора из корзины. Верните обработанную корзину.
Я реализовал простое решение, и оно прошло все простые тестовые случаи, однако не прошло все тестовые случаи с большими входными данными. В итоге у меня не было времени придумать более эффективное решение, лучше всего, я думаю, O(n²):
def problem_solution(items: list[int], query: list[int]) -> list[int]:
for item in query:
if item > 0:
items.append(item)
else:
items.remove(abs(item))
return items
Я думал об использовании collections.deque или collections.defaultdict, но не видел, как реально повысить эффективность. Что мне здесь не хватает?
Ошибка перевода, я имел в виду модуль. Да, я знаю, что удаление — это проблема, но не могу придумать лучшего решения. Я тоже не могу понять, почему меня минусуют.
Я не знаю, что означает «пример модуля ID». У вас есть формула? Кажется, это предполагает что-то связанное с модульной арифметикой, но ваш код вызывает abs, а это нечто иное.
Я имею в виду, например: запрос = [1] -> добавить 1 к элементам, запрос = [-1] -> удалить первый экземпляр 1 из элементов.
Ответы 1
Одной из идей было бы отложить удаление до тех пор, пока не будут обработаны все запросы, и регистрировать только то, сколько каждого значения должно быть удалено (в словаре).
Затем, после обработки запросов, перебираем собранные элементы и, пока текущее значение должно быть удалено, пропускаем его и в то же время уменьшаем количество удалений, которое у нас есть для этого элемента. Вы можете сделать это на месте, в списке items, и сдвигать значения влево при их посещении. В конце сократите список:
from collections import defaultdict
def problem_solution(items: list[int], query: list[int]) -> list[int]:
deleted_count = defaultdict(int)
for item in query:
if item > 0:
items.append(item)
else:
deleted_count[-item] += 1
i = 0
for item in items:
if deleted_count.get(item, 0) > 0:
deleted_count[item] -= 1
else:
items[i] = item
i += 1
del items[i:]
return items
NB: Поскольку это изменяет items, заданный в качестве аргумента, нет необходимости фактически возвращать его.
items.remove(n) — медленная операция, если список длинный, а n маленькое. Не уверен, что вы подразумеваете под «модулем идентификатора».