Python中countPerformer函数计算列表相似度得分结果不符问题

问题分析 #

当前代码存在两个核心问题，导致得分低于预期：

1. 元素位置查找范围错误：
   代码处理位置不同的元素时，仅从当前索引i开始向后遍历col2，完全忽略了元素在col2中位于i左侧（即j < i）的情况。比如col1[1]的元素2在col2[0]、col1[3]的元素4在col2[2]，这些情况都未被统计，直接丢失对应得分。

2. 得分规则计算错误：
   按照规则，位置不同的元素偏离n位应加n+1分，但代码仅累加了j-i（即n），少加了基础的1分。比如元素1偏离1位，应加2分，代码只加了1分。

预期得分拆解（验证） #

针对测试用例逐项计算：

• 元素1：偏离1位 → 2分
• 元素2：偏离1位 → 2分
• 元素3：偏离2位 → 3分
• 元素4：偏离1位 → 2分
• 元素5：偏离1位 → 2分
• 元素6~20：位置完全匹配，共15个元素 → 15分
  总分：2+2+3+2+2+15=26，与预期一致。

修正后的代码 #

def countPerformer(col1, col2):
    count = 0
    # 预建立col2元素到索引的映射，避免重复遍历查找
    element_index = {val: idx for idx, val in enumerate(col2)}
    for i in range(len(col1)):
        val = col1[i]
        j = element_index[val]
        if i == j:
            count += 1
        else:
            # 严格按规则计算：偏离位数绝对值 +1
            count += abs(j - i) + 1
    return count


col1 = list(range(1, 21))
col2 = [2, 1, 4, 5, 3, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
print(countPerformer(col1, col2)) # 输出26，符合预期

修正说明 #

• 用字典element_index预先存储col2元素的索引，将查找复杂度从O(n)降至O(1)，同时避免遗漏左侧位置的元素。
• 严格遵循规则计算得分：位置匹配加1分；位置不同时，取偏离位数的绝对值加1累加得分。

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