只有 63% 的分数，而不是 100% - Python 程序

Question

我有一个 python3 程序，它是正确的，它给出了正确的结果，但我想提高这个程序的时间复杂度。 当我在平台上运行它时，我最多只能得到 63% 的分数，而不是 100%，因为有些测试需要很长时间。

问题陈述

在整数列表中，重复是一对彼此相邻的相等数字。例如，在列表 1 3 3 4 2 2 1 1 1 中，有四个重复：两个 3，然后是两个 2，然后是后面的两个 1，最后是列表末尾的两个 1。

您将获得一个整数列表。编写一个程序，计算删除其中一个数字的所有出现后可以保留在列表中的最小重复次数。

输出

您应该输出一个数字：删除列表中所有出现的数字之一后可以保留的最小重复次数。

示例

以下是输入示例：

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

9个数字的列表是“1 3 2 2 3 4 4 2 1”。它包含两次重复（前两个 2 和两个 4）：

• 删除 1 留下两个重复；
• 删除 2 会将 3 放在一起，因此我们删除了一个重复并添加了一个。还剩两次重复；
• 删除 3 留下两个重复；
• 去掉 4 就只剩下一个重复。

如果我们删除所有出现的数字 4，则只剩下一个重复项。不可能得到比这个更少的数据，所以你的程序应该输出：

1

限制

• 时间限制：1000毫秒。
• 内存限制：64,000 kb。

设置时间限制，以便在整个列表上迭代少量次数的解决方案可以获得满分，但是对于列表中的每个数字，循环列表中的所有其他数字的解决方案只能解决大约一半测试不超过时间限制。

解决方案1

lst = [1, 3, 2, 2, 3, 4, 4, 2, 1]
# lst = [1,3,3,4,2,2,1,1,1]

def count_repetitions(lst):
    count = 0
    for i in range(1, len(lst)):
        if lst[i] == lst[i - 1]:
            count += 1
    return count


unique_numbers = set(lst)
min_repetitions = float('inf')

for num in unique_numbers:
    filtered_list = [x for x in lst if x != num]
    repetitions = count_repetitions(filtered_list)
    min_repetitions = min(min_repetitions, repetitions)

print(min_repetitions)

解决方案2

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

repmin=100000
listunique =[]

for v in liste:
    if v not in listunique:
        listunique.append(v)

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
  if rep<repmin:
    repmin=rep

print(repmin)

如何提高这个问题的时间复杂度，让程序运行得更快。

提前致谢

Answer 1

线性时间：

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())