我用 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
最佳答案
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
总重复次数,以及对于每个值,删除该值将删除多少次重复次数。
顺便说一句,将它放入函数中可以使变量更快,并使测试更容易(如果单击链接,您将看到一些测试)。
|
–
–
–
–
–
|