求解使两个数组元素频率相同的最少操作次数

首先得明确操作的核心特性，这是解题的关键：

• 操作不改变数组B的总和：每次操作的+2和-2相互抵消，数组总和始终不变。
• 操作不改变元素的奇偶性：加减2不会影响元素模2的结果，因此奇数只能调整为奇数，偶数只能调整为偶数。

基于这两个特性，我们可以分步骤判断可行性并计算最少操作次数：

步骤1：基础可行性判断 #

• 计算数组A和B的总和，若不相等，直接返回-1（无论多少次操作都无法让两者元素频率一致）。
• 将A、B拆分为奇数列表和偶数列表：A_odd、A_even、B_odd、B_even。若len(A_odd) != len(B_odd)，返回-1（奇偶元素数量不匹配，无法通过操作调整到目标状态）。

步骤2：计算最少操作次数 #

• 分别对A_odd与B_odd、A_even与B_even进行排序。排序的目的是让需要调整的元素一一对应（只有同奇偶的元素之间才能互相转移增量）。
• 遍历每一对对应元素，计算(A元素 - B元素) // 2：这个值表示B元素需要增加多少个“2”（正数）或减少多少个“2”（负数）才能匹配A元素。
• 统计所有正数的总和，这个总和就是最少操作次数。因为每次操作可以同时处理一个+1和一个-1（对应原操作的+2和-2），所有正增量的总和恰好等于需要执行的操作次数。

示例验证 #

以题目中的输入为例：

• A总和：2+10+14=26；B总和：6+2+18=26，符合条件。
• A全为偶数，B全为偶数，奇偶数量匹配。
• 排序后A_even = [2,10,14]，B_even = [2,6,18]。
• 计算每对的差值除以2：(2-2)/2=0，(10-6)/2=2，(14-18)/2=-2。
• 正数总和为2，即需要2次操作，与题目输出一致。

代码实现（Python） #

def min_operations(A, B):
    # 检查总和是否相等
    if sum(A) != sum(B):
        return -1
    
    # 拆分奇偶列表
    def split_odd_even(arr):
        odd = []
        even = []
        for num in arr:
            odd.append(num) if num % 2 else even.append(num)
        return odd, even
    
    a_odd, a_even = split_odd_even(A)
    b_odd, b_even = split_odd_even(B)
    
    # 检查奇偶数量是否匹配
    if len(a_odd) != len(b_odd):
        return -1
    
    # 排序对应列表
    a_odd.sort()
    b_odd.sort()
    a_even.sort()
    b_even.sort()
    
    operations = 0
    # 处理奇数对的增量
    for a, b in zip(a_odd, b_odd):
        diff = (a - b) // 2
        if diff > 0:
            operations += diff
    # 处理偶数对的增量
    for a, b in zip(a_even, b_even):
        diff = (a - b) // 2
        if diff > 0:
            operations += diff
    
    return operations

# 测试题目示例
A = [2, 10, 14]
B = [6, 2, 18]
print(min_operations(A, B))  # 输出2

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