环形数组相邻替换全相等最小步数代码边缘用例排查

问题描述 #

给定包含N个整数的环形数组A，可对数组执行任意次如下操作：

• 对每个下标i，可将A[i]替换为A[i-1]、A[i]或A[i+1]，即可保留当前元素，或替换为相邻元素。由于数组为环形结构，首尾元素同样存在相邻关系，特别地，i=0时A[i-1]为数组最后一个元素。
  请计算使数组所有元素相等所需的最小操作步数。

输入格式 #

• 第一行输入整数N，表示数组A的元素个数
• 后续N行（0≤i<N）每行输入一个整数，对应A[i]的取值

约束条件 #

• 1 ≤ N ≤ 10^3

样例说明 #

• 输入4 2 2 1 1，输出1
• 输入3 1 1 1，输出0
• 输入4 1 2 3 4，输出2

原代码存在的明确缺陷 #

1. 核心目标选择逻辑错误
   原代码默认选择出现频次最高的元素作为最终统一的目标值，该逻辑完全不成立。最小步数的本质是：找一类元素的位置分布，让数组所有位置到最近该类元素的最大距离最小，和元素出现总次数没有必然正相关关系。
   举个可复现的错误case：数组[1,2,1,2,1,3,3,3]，元素1和3都出现3次，为最高频次。原代码会选遍历顺序靠后的3作为目标值，计算得到需要3步操作，但实际选1作为目标值仅需要2步，原代码直接返回错误结果。
2. 同频次候选值对比缺失
   当多个元素出现频次相同时，原代码仅取遍历过程中最后遇到的同频次元素计算步数，完全不对比其他同频次、甚至低频次但分布更优的元素的步数，结果必然存在偏差。
3. 基础输入逻辑缺失
   原代码最后直接调用make_equal(A)，但全程没有定义变量A、也没有写标准输入读取逻辑，在评测机环境下运行会直接抛出变量未定义的错误，这也是隐藏用例无法通过的低级问题。
4. 扩散计算逻辑冗余
   原代码的BFS扩散过程每次循环都会重复追加已经存在的下标到列表中，虽然用set做了去重，但N达到1e3量级时会产生大量无效数据，运行效率极低。
5. 边缘场景覆盖不足
   原代码没有对N=1的边界场景做适配，当数组只有1个元素时，虽然计算结果大概率为0，但环形索引计算存在潜在的逻辑风险。

正确解题思路 #

• 首先遍历数组，把每个不同值对应的所有下标按顺序分组存储
• 由于数组是环形结构，对每个值的下标列表，复制一份所有下标并加上数组长度N，拼接在原列表后面，用来处理首尾相邻的边界情况
• 对每个值，计算相邻两个同值下标的间隔，最大间隔除以2（向下取整）就是把整个数组变成该值需要的最小步数
• 所有候选值对应的步数取最小值，就是最终答案

可通过全部测试用例的参考代码 #

from collections import defaultdict

def make_equal(A):
    n = len(A)
    if n <= 1:
        return 0
    pos_map = defaultdict(list)
    for idx, val in enumerate(A):
        pos_map[val].append(idx)
    min_step = float('inf')
    for positions in pos_map.values():
        # 扩展下标处理环形边界
        ext_pos = positions + [p + n for p in positions]
        max_gap = 0
        for i in range(len(positions)):
            current_gap = ext_pos[i+1] - ext_pos[i]
            if current_gap > max_gap:
                max_gap = current_gap
        # 最大间隔的一半就是当前值需要的步数
        current_step = max_gap // 2
        if current_step < min_step:
            min_step = current_step
    return min_step

if __name__ == "__main__":
    import sys
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    A = list(map(int, input_data[1:N+1]))
    print(make_equal(A))

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