Python3算法优化求助：降低O(n²)复杂度以通过全量测试

问题背景 #

用Python3编写的程序结果正确，但时间复杂度为O(n²)，在Algorea平台仅通过16个测试用例中的10个（63%），部分测试因超时无法通过，需优化算法效率。

问题描述 #

在整数列表中，重复指相邻的相等数对。例如列表[1,3,3,4,2,2,1,1,1]中有4个重复：两个3、两个2、随后的两个1、末尾的两个1。给定整数列表，计算移除某一数字的所有出现后，列表中剩余的最小重复数。

输出要求 #

输出移除某一数字所有出现后，列表剩余的最小重复数。

示例 #

输入列表：

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

原列表有2个重复（两个2、两个4）：

• 移除1后仍剩2个重复；
• 移除2后3相邻，移除1个重复但新增1个，仍剩2个；
• 移除3后仍剩2个重复；
• 移除4后仅剩1个重复。
  因此输出为1。

约束条件 #

• 时间限制：1000ms
• 内存限制：64000kb

原解法（O(n²)复杂度） #

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

优化思路（时间复杂度降至O(n)） #

原解法的核心问题是对每个唯一元素都重新遍历列表生成新列表并统计重复数，导致O(k*n)的时间复杂度（k为唯一元素数量），最坏情况下k接近n时退化为O(n²)。

优化核心是预先统计原列表的重复总数，再计算移除每个元素时对重复数的影响，无需重新生成列表：

1. 一次遍历列表，计算原总重复数total_repeats；
2. 遍历列表，统计每个元素x对应的两个关键值：
   • lost：移除x后会消失的重复数（即相邻两个元素都是x的对数）；
   • gained：移除x后会新增的重复数（即x的左右邻居为相同非x元素的次数）；
3. 对每个唯一元素x，移除后的重复数为total_repeats - lost[x] + gained[x]，取所有结果的最小值即为答案。

优化后代码 #

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

if not liste:
    print(0)
    exit()

# 计算原列表总重复数
total_repeats = 0
for i in range(len(liste)-1):
    if liste[i] == liste[i+1]:
        total_repeats += 1

# 统计每个元素对应的lost和gained值
from collections import defaultdict
lost = defaultdict(int)
gained = defaultdict(int)

for i in range(len(liste)):
    x = liste[i]
    # 统计lost：当前元素与下一个元素都是x的情况
    if i < len(liste)-1 and liste[i] == liste[i+1]:
        lost[x] += 1
    # 统计gained：当前元素是x，左右邻居相同且不是x的情况
    if 0 < i < len(liste)-1:
        left = liste[i-1]
        right = liste[i+1]
        if left == right and left != x:
            gained[x] += 1

# 计算每个元素被移除后的重复数，取最小值
unique_elements = set(liste)
min_repeats = float('inf')
for x in unique_elements:
    current = total_repeats - lost[x] + gained[x]
    if current < min_repeats:
        min_repeats = current

print(min_repeats)

复杂度说明 #

• 时间复杂度：O(n)，仅需三次线性遍历列表，所有操作均为常数级；
• 空间复杂度：O(k)，k为列表中唯一元素的数量，空间占用远低于原解法。

内容的提问来源于stack exchange，提问作者Mourad BENKDOUR