我用 python3 编写了一个程序，它是正确的，它给出了正确的结果，但它的时间复杂度为 O(n^2)。我想提高这个程序的时间复杂度。当我在平台上运行它时 ，该程序仅通过了 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))

我怎样才能提高这个问题的时间复杂度，让程序运行得更快。

提前致谢

9

  • 5
    你指的是什么“分数”？是什么让你认为你可以提高时间复杂度（这与加快速度不同）？


    – 

  • 4
    您在哪里测试这个？我们可以自己在那里测试潜在的解决方案吗？


    – 

  • 3
    每个 Stack Overflow 问题都应该严格地集中在一个特定的技术问题上，这样遇到该问题的人即使编写的是完全不同类型的程序，也可以从问题的答案中阅读和学习。如果你在这里有一个通用或可概括的问题，那么它是什么就不太清楚了。


    – 

  • 1
    @nocomment 算法问题如果不是非常简单的话，往往会被关闭（尤其是当大多数人想不出更快的算法时）。如果标记了特定语言，情况会更糟。


    – 


  • 2
    我不同意这是滥用——这是按设计工作。请参阅从一开始就阐明 SO 的意图（本质上是一个巨大的常见问题解答）。我无法想象这个问题或那个问题在常见问题解答中有意义。（就此而言，在早期，我们有一个“过于本地化”的关闭原因，它非常适合那些无法推广到其他人的问题/未能提取更广泛适用的根本问题）


    – 



最佳答案
2

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

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

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

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

线性时间（）：

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总重复次数，以及对于每个值，删除该值将删除多少次重复次数。

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