求将偶数长度数组转为优美数组所需最少操作次数的正确解法

核心思路 #

该问题本质是无向图连通分量统计问题，核心逻辑是：需要统一为相同值的数字必然属于同一个连通块，每个大小为k的连通块最少需要k-1次修改操作。

具体步骤 #

• 第一步：拆分位置对
  将数组拆分为长度相等的前后两半，遍历每个对应位置，取出左半值l = arr[i]、右半值r = arr[i + n/2]，如果l == r无需处理，直接跳过。
• 第二步：构建关联关系
  对于每一组l != r的无序对，将l和r建立关联，代表两个值最终需要统一为同一个值。
• 第三步：统计连通分量
  遍历所有出现过的非配对值，统计每个连通分量的大小k。
• 第四步：计算最终结果
  每个连通分量需要的最少操作次数为k-1，所有连通分量的k-1之和就是最终答案。

正确性验证 #

以题目给出的示例数组[1, 1, 2, 5, 2, 5, 5, 2]验证：

1. 拆分得到的不等对为(1,2)、(1,5)、(2,5)、(5,2)
2. 所有值1、2、5属于同一个连通分量，大小为3
3. 最少操作次数为3-1=2，和预期一致。

参考实现（Python） #

def min_operations(arr):
    n = len(arr)
    half = n // 2
    # 数值范围为1~1e5，初始化并查集
    parent = list(range(100001))
    exist_val = set()
    
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    def union(x, y):
        rx, ry = find(x), find(y)
        if rx != ry:
            parent[ry] = rx
    
    for i in range(half):
        l, r = arr[i], arr[i + half]
        if l == r:
            continue
        union(l, r)
        exist_val.add(l)
        exist_val.add(r)
    
    # 统计各连通分量大小
    comp_size = {}
    for num in exist_val:
        root = find(num)
        comp_size[root] = comp_size.get(root, 0) + 1
    
    return sum(k - 1 for k in comp_size.values())

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