通过删除所有出现的一个数字来最大限度地减少重复

Question

我用 python3 做了一个程序，它是正确的，它给出了正确的结果，但它的时间复杂度为 O(n^2)。我想提高这个程序的时间复杂度。 当我在 algorea 平台上运行它时，程序仅通过了 63% 的测试（16 个测试中仅通过了 10 个），因为某些测试需要很长时间。 你能给我一个更好更高效的算法吗？

问题陈述

在整数列表中，重复是一对彼此相邻的相等数字。例如，在列表 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。

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

我的解决方案

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

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

提前致谢

Answer 1

为了降低时间复杂度，您需要尽可能少地进行迭代。理想情况下，只需迭代列表一次，并从一次读取中收集所有数据。

由于一次只能消除一位数字，因此您可以存储一些以前的值，以便检查如果当前值是被消除的数字，是否会创建新的重复。

考虑一个程序结构，其中：

• 初始化字典以跟踪与每个数字的消除相对应的重复（例如示例列表中的 dict["1"] = 2，因为删除 1 将导致 2 次重复）
• 对于列表中每个已处理的数字，检查前一个和下一个值（如果存在）以确定其消除是否会导致新的重复。如果可以，请增加字典中数字键的值
• 同时记录列表中预先存在的重复次数并将其存储为“总重复次数”值
• 当您发现这些预先存在的重复之一时，递减相应数字的字典值的计数器（因为删除该数字将因此删除重复）
• 一旦列表被完全迭代，字典实际上记录了每个数字的消除对重复次数的净影响。如果 dict[4] 返回 -3，则意味着从列表中删除 4 将使重复总数减少 3
• 返回预先存在的重复次数减去字典中保存的最小值

Answer 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

、重复总数，以及对于每个值，删除会删除多少重复。

顺便说一句，将其放入函数中可以使变量更快并使测试更容易（如果单击链接，您将看到一些测试）。