如何解决两数组补零平衡后求最小和的算法问题？

算法思路 #

要解决这个问题，我们需要通过补全数组中的0（补入正整数），让两个数组的和相等，同时使这个相等的和尽可能小。核心是基于数组的非0元素和、0的数量，分情况推导可行的最小目标和。

具体步骤 #

1. 计算基础参数

   • 分别计算两个数组的非0元素之和：sum1（数组a1）、sum2（数组a2）
   • 统计两个数组中0的个数：cnt1（数组a1）、cnt2（数组a2）

2. 分场景处理

   • 场景1：两个数组都没有0
     直接比较sum1和sum2：相等则返回该和，否则返回-1。
   • 场景2：只有一个数组包含0
     • 若仅a1有0：需要a2的固定和sum2大于等于a1补全后的最小和sum1 + cnt1，且sum2 - sum1 >= cnt1（保证a1的每个0至少补1）。满足则返回sum2，否则返回-1。
     • 若仅a2有0：需要a1的固定和sum1大于等于a2补全后的最小和sum2 + cnt2，且sum1 - sum2 >= cnt2。满足则返回sum1，否则返回-1。
   • 场景3：两个数组都包含0
     最小的目标和就是两个数组补全0后的最小可能和的较大值，即max(sum1 + cnt1, sum2 + cnt2)。因为：
     • 若sum1 + cnt1 >= sum2 + cnt2：a1的每个0补1即可达到该目标和，a2的补全总和为目标和 - sum2，该值必然大于等于cnt2（满足每个0至少补1的要求）。
     • 反之同理，a2的每个0补1达到目标和，a1的补全总和也满足要求。

代码实现（Python） #

def min_equal_sum(a1, a2):
    sum1 = sum(x for x in a1 if x != 0)
    sum2 = sum(x for x in a2 if x != 0)
    cnt1 = a1.count(0)
    cnt2 = a2.count(0)
    
    # 场景1：无0
    if cnt1 == 0 and cnt2 == 0:
        return sum1 if sum1 == sum2 else -1
    # 场景2：仅一个数组有0
    elif cnt1 == 0:
        if sum1 >= sum2 and (sum1 - sum2) >= cnt2:
            return sum1
        else:
            return -1
    elif cnt2 == 0:
        if sum2 >= sum1 and (sum2 - sum1) >= cnt1:
            return sum2
        else:
            return -1
    # 场景3：两个数组都有0
    else:
        return max(sum1 + cnt1, sum2 + cnt2)

示例验证 #

• 示例1：a1 = [1,0,3]，a2 = [1,4,0,0]
sum1=4，cnt1=1；sum2=5，cnt2=2。sum1+cnt1=5，sum2+cnt2=7，返回7，符合预期。
• 示例2：a1 = [1,2]，a2 = [4,0]
sum1=3，cnt1=0；sum2=4，cnt2=1。sum1 < sum2，不满足条件，返回-1，符合预期。

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