Минимизируйте повторы, удалив все вхождения одного числа
Я написал программу на Python3, и это правильно, она дает правильные результаты, но ее временная сложность равна O (n^2). Я хочу улучшить временную сложность этой программы. Когда я запускаю ее на платформе algorea, программа проходит только 63% тестов (только 10 из 16 тестов), потому что некоторые тесты занимают много времени. Не могли бы вы дать мне лучший и эффективный алгоритм?
Постановка задачи
В списке целых чисел повторение — это пара одинаковых чисел, расположенных рядом друг с другом. Например, в списке 1 3 3 4 2 2 1 1 1 четыре повторения: две тройки, затем две двойки, затем следующие две единицы и, наконец, две единицы в конце списка.
Вам дан список целых чисел. Напишите программу, которая вычисляет минимальное количество повторений, которое может остаться в списке после удаления всех вхождений одного из чисел.
Выход
Вам следует вывести единственное число: минимальное количество повторений, которое может остаться после удаления всех вхождений одного из чисел в списке.
Примеры
Вот пример ввода:
liste = [1, 3, 2, 2, 3, 4, 4, 2, 1]
Список из 9 чисел: «1 3 2 2 3 4 4 2 1». Он содержит два повторения (первые две двойки и две четверки):
- Удаление единиц оставляет два повторения;
- Удаление двойок объединяет тройки, поэтому мы удалили одно повторение и добавили одно. Осталось еще два повторения;
- Удаление троек оставляет два повторения;
- Удаление четверок оставляет только одно повторение.
Если мы удалим все вхождения числа 4, останется только одно повторение. Получить меньшее значение невозможно, поэтому ваша программа должна вывести:
1
Ограничения
- Ограничение по времени: 1000 мс.
- Ограничение памяти: 64 000 Кб.
Ограничение по времени установлено таким образом, что решение, которое повторяется небольшое количество раз по всему списку, может набрать полные баллы, но решение, которое для каждого числа в списке перебирает все остальные числа в списке, может решить только около половины испытания без превышения лимита времени.
Мое решение
liste = [1, 3, 2, 2, 3, 4, 4, 2, 1]
# liste = [1,3,3,4,2,2,1,1,1]
repmin=[]
listunique =set(liste)
for x in listunique:
listWithoutx = []
for i in liste:
if i!=x:
listWithoutx.append(i)
rep=0
for j in range(len(listWithoutx)-1):
if listWithoutx[j]==listWithoutx[j+1]:
rep+=1
repmin.append(rep)
print(min(repmin))
Как я могу улучшить временную сложность этой задачи, например, чтобы программа работала быстро.
заранее спасибо
Где вы это проверяете? Можем ли мы сами протестировать там потенциальные решения?
Каждый вопрос о переполнении стека должен быть узко сфокусирован на конкретной технической проблеме, чтобы люди, столкнувшиеся с этой проблемой, могли читать ответы на вопросы и учиться на них, даже если они пишут программу совершенно другого типа. Если у вас здесь обобщенный или обобщающий вопрос, то не очень понятно, что это такое.
@CharlesDuffy Чем он отличается, например, от этого вопроса, набравшего более 4000 голосов?
@nocomment Вопросы по алгоритмам, как правило, все время закрываются, если они не очень простые (особенно когда большинство людей не могут придумать более быстрый алгоритм). Ситуация ухудшается, если помечен конкретный язык.
@ Абсолютная грусть. Похоже на злоупотребление системой.
Я не согласен с тем, что это злоупотребление — все работает так, как задумано. См. stackoverflow.blog/2011/01/05/… с самого начала, каким должен был быть SO (по сути, огромный FAQ). Я не мог себе представить, чтобы тот или иной вопрос имел смысл в FAQ. (Если уж на то пошло, то в самом начале у нас была «слишком локализованная» близкая причина, которая идеально подходила для проблем, которые нельзя было обобщить, чтобы они были полезны другим, / не удалось выявить более широко применимую основную проблему)
@CharlesDuffy Эта статья была написана 13 лет назад. И тысячи людей, объявляющих этот другой вопрос полезным, показывают, что он имеет ценность. Я думаю, что и этот тоже. И близкая причина выглядит фальшивой, на этот вопрос легко ответить как есть.
@ScottHunter это около 63% тестов (Моя программа проходит только 10 из 16 тестов), потому что моей программе требуется много времени для решения 6 тестов
@nocomment, как сообщение, на которое есть ссылка, чтобы показать, что текущая интерпретация правил соответствует первоначальному намерению («с самого начала»), не относится к этому первоначальному намерению? Да, он старый (и написан лично основателем SO); это преднамеренный элемент его актуальности.
@CharlesDuffy Кого волнует первоначальный замысел? Меня волнуют текущие намерения. И что-то столь старое может оказаться столь же устаревшим, как и «слишком локализованное».
Ответы 2
Линейное время (Попробуйте это онлайн!):
def min_repetitions(lst):
total = 0
remove = dict.fromkeys(lst, 0)
a = b = None
for c in lst:
if c == b:
total += 1
remove[c] += 1
else:
if c == a:
remove[b] -= 1
a = b
b = c
return total - max(remove.values())
Это отслеживает последние три значения без повторений как a, b и c, общее количество повторений и для каждого значения, сколько повторений будет удалено при его удалении.
Кстати, размещение его в функции ускоряет работу с переменными и упрощает тестирование (вы увидите некоторые тесты, если щелкните ссылку).
Большое спасибо, ваше решение потрясающее.
Знаете ли вы какие-нибудь ресурсы (Youtube, учебные пособия, книги...), чтобы научиться писать эффективный код и алгоритм оптимизации с наилучшей временной сложностью?
@MouradBENKDOUR Такие сайты, как LeetCode и т. д., могут помочь. Но я занимаюсь этим уже более 25 лет, брал или придумывал вещи в самых разных местах.
Чтобы уменьшить временную сложность, вам нужно делать как можно меньше итераций. В идеале перебирайте список только один раз и собирайте все данные за одно чтение.
Поскольку вы можете удалять только одну цифру за раз, вы можете сохранить несколько предыдущих значений, чтобы проверить, будет ли создано новое повторение, если текущее значение является тем, которое было удалено.
Рассмотрим структуру программы, в которой:
- Словарь инициализируется для отслеживания повторений, соответствующих исключению каждого числа (например, dict["1"] = 2 в вашем списке примеров, поскольку удаление единиц приведет к 2 повторениям)
- Для каждого обработанного числа в списке проверьте предыдущее и следующее значения (если они существуют), чтобы определить, приведет ли его удаление к новому повторению. Если да, увеличьте значение числового ключа в словаре.
- Одновременно вести подсчет ранее существовавших повторений в списке и сохранять его как значение «общее количество повторений».
- Когда вы найдете одно из этих ранее существовавших повторений, уменьшите счетчик значения dict соответствующего числа (поскольку удаление этого числа приведет к удалению повторения).
- После того, как список полностью пройден, словарь фактически представляет собой запись общего эффекта на количество повторений, которое может вызвать исключение каждого числа. Если dict[4] вернул -3, то это означает, что исключение 4 из списка уменьшит общее количество повторений на 3.
- Вернуть количество ранее существовавших повторений минус наименьшее значение, содержащееся в словаре.
О каком «счете» вы говорите? Что заставляет вас думать, что вы можете улучшить временную сложность (что не то же самое, что сделать ее быстрее)?