Минимизируйте повторы, удалив все вхождения одного числа. ⇐ Python

[Anonymous]

Я написал программу на Python3, и это правильно, она дает правильные результаты, но ее временная сложность равна O(n^2). Я хочу улучшить временную сложность этой программы.
Когда я запускаю ее на платформе Algorea, программа проходит только 63% тестов (только 10 из 16 тестов), потому что некоторые тесты занимают много времени.
Не могли бы вы дать мне лучший и эффективный алгоритм?
Постановка задачи
В списке целых чисел повторение — это пара равных чисел, которые примыкают друг к другу. Например, в списке 1 3 3 4 2 2 1 1 1 четыре повторения: две тройки, затем две двойки, затем две последующие единицы и, наконец, две единицы в конце списка.< /p>
Вам дан список целых чисел. Напишите программу, которая вычисляет минимальное количество повторений, которое может остаться в списке после удаления всех вхождений одного из чисел.
Вывод
Вам следует вывести одно число: минимальное количество повторений, которое может остаться после удаления всех вхождений одного из чисел в списке.
Примеры
Вот пример ввода:

Код: Выделить всё

liste = [1, 3, 2, 2, 3, 4, 4, 2, 1]

Список из 9 чисел: «1 3 2 2 3 4 4 2 1». Он содержит два повторения (первые две двойки и две четверки):

• При удалении единиц остаются два повторения;
  < li>Удаление двойок объединяет тройки, поэтому мы удалили одно повторение и добавили одно. Осталось еще два повторения;
• Удаление троек оставляет два повторения;
• Удаление четверок оставляет только одно повторение.

Если удалить все вхождения числа 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))

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

Подробнее здесь: https://stackoverflow.com/questions/786 ... one-number