Python中寻找数据集的最小不匹配三元组问题

给定一个升序排列的40位数字列表（天然满足三元组A<=B<=C的要求），k=1，需要找出所有具有最小不匹配度的三元组(A,B,C)，其中不匹配度由(A-B)²定义，C的取值不影响结果。

列表数据：

list1 = [1, 8, 10, 16, 19, 22, 27, 33, 36, 40, 47, 52, 56, 61, 63, 71, 72, 75, 81, 81, 84, 88, 96, 98, 103, 110, 113, 118, 124, 128, 129, 134, 134, 139, 148, 157, 157, 160, 162, 164]

原代码的问题 #

你最初生成三元组和计算差值的逻辑是正确的，但后续移除元素的代码存在明显错误：

# 错误代码
for i in res:
    if res[i] > res[i+1]:
        res.pop(i)
        result.pop(i)

• 遍历的是res的元素而非索引，i是元素值不是索引，会导致索引越界或错误访问
• 遍历列表时直接删除元素，会打乱列表长度和后续索引，导致漏处理或报错

正确解决方案 #

核心思路 #

1. 生成所有连续三元组（因列表升序，天然满足A<=B<=C）
2. 计算每个三元组的不匹配度（abs(B-A)与(B-A)²的最小值等价，计算更高效）
3. 找到最小不匹配度值
4. 筛选出所有不匹配度等于最小值的三元组

实现代码 #

list1 = [1, 8, 10, 16, 19, 22, 27, 33, 36, 40, 47, 52, 56, 61, 63, 71, 72, 75, 81, 81, 84, 88, 96, 98, 103, 110, 113, 118, 124, 128, 129, 134, 134, 139, 148, 157, 157, 160, 162, 164]

# 生成所有连续三元组
triples = list(zip(list1, list1[1:], list1[2:]))

# 计算每个三元组的不匹配度（用绝对值等价于平方的最小值）
mismatches = [abs(b - a) for a, b, c in triples]

# 找到最小不匹配度
min_mismatch = min(mismatches)

# 筛选符合条件的三元组
mismatchList = [triple for triple, mm in zip(triples, mismatches) if mm == min_mismatch]

print(mismatchList)

运行结果 #

输出与你期望的一致：

[(8, 10, 16), (19, 22, 27), (61, 63, 75), (71, 72, 88), (81, 81, 84), (96, 98, 103), (128, 129, 148), (134, 134, 139), (157, 157, 160)]

说明 #

• 无需递归移除元素，直接找最小值再筛选是最直观高效的方式，时间复杂度为O(n)
• 因列表已升序，所有生成的三元组自动满足A<=B<=C的要求

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