环形数组相邻元素替换致全相等的最小步数求解及代码求助

你之前用HashMap统计最高频率元素的思路不对，因为这个问题的核心不是元素出现次数，而是环形数组中，每个元素要变成目标值的最小扩散步数——每一步操作中，元素只能替换成相邻位置的当前值，相当于目标值的“影响范围”每一步能向左右扩展1个位置。我们需要找到一个目标值，让它的影响范围覆盖整个数组所需的步数最少。

核心思路 #

1. 对于数组中的每个不同元素，收集它在数组中的所有位置；
2. 针对每个元素的位置列表，计算环形数组中相邻两个位置（包括最后一个位置和第一个位置的环形相邻）之间的间隔；
3. 每个间隔对应的最大扩散步数是 间隔长度 // 2（比如间隔3个元素，最大需要1步就能覆盖；间隔4个元素，最大需要2步）；
4. 取所有间隔的最大步数作为该元素的总步数，最终在所有元素的总步数中取最小值，就是答案。

代码实现 #

from collections import defaultdict

n = int(input())
arr = [int(input()) for _ in range(n)]

# 统计每个元素对应的所有位置
pos_dict = defaultdict(list)
for idx, num in enumerate(arr):
    pos_dict[num].append(idx)

min_total_steps = float('inf')

# 遍历每个可能的目标元素
for target in pos_dict:
    positions = pos_dict[target]
    count = len(positions)
    max_step = 0
    
    for i in range(count):
        # 计算当前位置与下一个位置的环形距离
        if i < count - 1:
            gap = positions[i+1] - positions[i]
        else:
            # 处理环形的最后一个位置到第一个位置的距离
            gap = (positions[0] + n) - positions[i]
        
        # 该间隔需要的最大步数
        current_step = gap // 2
        if current_step > max_step:
            max_step = current_step
    
    # 更新最小步数
    if max_step < min_total_steps:
        min_total_steps = max_step

print(min_total_steps)

代码说明 #

• 用defaultdict统计每个元素的所有出现位置，方便后续计算间隔；
• 针对每个元素的位置列表，遍历计算相邻位置的环形间隔：最后一个位置的下一个位置是第一个位置加上数组长度，模拟环形特性；
• 每个间隔的最大步数是间隔长度整除2，因为目标值从两端向中间扩散，最多需要间隔//2步就能覆盖整个间隔；
• 最终取所有元素对应的最大步数中的最小值，就是让数组所有元素相等的最少操作次数。

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