Leetcode 2918.数组的最小和

前言

本题出自Leetcode周赛 369场

原题链接2918.数组的最小相等和

本题不需要任何算法 一个纯分类讨论题目

题目描述

给你两个由正整数和 0 组成的数组 nums1 和 nums2 。

你必须将两个数组中的 所有 0 替换为 严格 正整数，并且满足两个数组中所有元素的和 相等 。

返回 最小 相等和 ，如果无法使两数组相等，则返回 -1 。

示例 1：
输入：nums1 = [3,2,0,1,0], nums2 = [6,5,0]
输出：12
解释：可以按下述方式替换数组中的 0 ：
- 用 2 和 4 替换 nums1 中的两个 0 。得到 nums1 = [3,2,2,1,4] 。
- 用 1 替换 nums2 中的一个 0 。得到 nums2 = [6,5,1] 。
两个数组的元素和相等，都等于 12 。可以证明这是可以获得的最小相等和。

示例 2：
输入：nums1 = [2,0,2,0], nums2 = [1,4]
输出：-1
解释：无法使两个数组的和相等。

数据范围

• 1 <= nums1.length, nums2.length <= 105
• 0 <= nums1[i], nums2[i] <= 106

解题思路

我们可以分成五种情况讨论

• 假设数组的和相等
• 假设nums1有0 nums2没0
• 假设nums1没0 nums2有0
• 两个数组都有0
• 两个数组都没0

先来看看第一种情况 如果两个数组和相等 我们需要判断nums1不包含0 == nums2不包含0 ,如果符合条件则直接返回任意一个数组和

第二种情况 设$i=nums2[n]+nums2[n+1]+nums2[n+2]....$，$j$为$nums1$数组中的0个数，$k=nums1[n]+nums1[n+1]....$ 如果$k>=i\mid(i-k)//j==0$则返回$-1$,否返回$nums2$的数组和

第三种情况 设$i=nums1[n]+nums1[n+1]+nums1[n+2]....$，$j$为$nums2$数组中的0个数，$k=nums2[n]+nums2[n+1]....$ 如果$k>=i\mid(i-k)//j==0$则返回$-1$,否返回$nums1$的数组和

关于这条公式的到来 我这里解释一下

假设$nums1 = [3,2,0,1,0], nums2 = [6,5,1]$ 可以看到第二个数组是没0的 第一个有两个零

第一个条件$k>=i$ 则说明 如果第一个数组还是0的情况 它的和已经大于第二个数组 显然是无法修改的 只能返回-1

在满足第一个条件之下 我们还要继续判断$(i-k)//j$意思是 求出两个数组的差 然后除于第一个数组的0的个数 校验一下是否能把第一个数组的所有0均匀分配 如果除出来是0说明第一个数组和第二个数组的和无法相等

第四种情况 先把$nums1$的0全部改成1 代入第二种情况 再反过来重复即可

注意:第四种情况 如果无法满足条件 不要返回-1 而是原始的答案 具体看下面的代码

第五种情况 直接判断和是否相等 相等返回其中一个$nums$的和 没则返回**-1**

现在看看代码怎么写

首先定义四个函数i,j,i_,j_

• $i$是$nums1$的和
• $j$是$nums2$的和
• $i\_$是$nums1$0的个数
• $j\_$是$nums2$0的个数

class Solution:
    def minSum(self, nums1: List[int], nums2: List[int]) -> int:
        i,j,i_,j_ = sum(nums1),sum(nums2),0,0
        for k in range(0,len(nums1)):
            if nums1[k] == 0:
                i_+=1
        for k in range(0,len(nums2)):
            if nums2[k] == 0:
                j_+=1

先来判断第一种情况和最后一种情况

class Solution:
    def minSum(self, nums1: List[int], nums2: List[int]) -> int:
        i,j,i_,j_ = sum(nums1),sum(nums2),0,0
        for k in range(0,len(nums1)):
            if nums1[k] == 0:
                i_+=1
        for k in range(0,len(nums2)):
            if nums2[k] == 0:
                j_+=1
        if i == j and i_ == 0 and j_ == 0:
            return i
        if i_ == 0 and j_ == 0:
            return i == j  

这里不能压缩两种情况,假设两个数组的数相同，左边没0右边有0，这种情况不适合

分别写入第二种情况和第三种情况

class Solution:
    def minSum(self, nums1: List[int], nums2: List[int]) -> int:
        i,j,i_,j_ = sum(nums1),sum(nums2),0,0
        for k in range(0,len(nums1)):
            if nums1[k] == 0:
                i_+=1
        for k in range(0,len(nums2)):
            if nums2[k] == 0:
                j_+=1
        if i == j and i_ == 0 and j_ == 0:
            return i
        if i_ == 0 and j_ == 0:
            return -1 if i != j else i
        if i_ == 0 and j_ != 0:
            return -1 if j >= i or (i-j)//j_ == 0 else i
        if i_ != 0 and j_ == 0:
            return -1 if i >= j or (j-i)//i_ == 0 else j

最后写第四种情况，定义ans为最终答案 并把ans初始化成10的11次方

先填充nums1然后代入公式 更新最小值 nums2同理

# 时间复杂度O(n)
# 空间复杂度O(1) 仅用了若干变量
class Solution:
    def minSum(self, nums1: List[int], nums2: List[int]) -> int:
        i,j,i_,j_ = sum(nums1),sum(nums2),0,0
        for k in range(0,len(nums1)):
            if nums1[k] == 0:
                i_+=1 # 先统计第一个数组0的个数
        for k in range(0,len(nums2)):
            if nums2[k] == 0:
                j_+=1 # 然后是第二个数组0的个数
        if i == j and i_ == 0 and j_ == 0:
            return i # 如果值相等 第一个数组和第二个数组都没0 则返回任意一个数组的和
        if i_ == 0 and j_ == 0:
            return -1 if i != j else i # 如果第一个和第二个都没0 则判断一下他们的和
        if i_ == 0 and j_ != 0:
            return -1 if j >= i or (i-j)//j_ == 0 else i # 第一个数组有0 第二个数组没0 代入公式求解即可
        if i_ != 0 and j_ == 0:
            return -1 if i >= j or (j-i)//i_ == 0 else j # 第一个数组没0 第二个数组有0 代入公式求解即可
        o = 10 ** 11 # 初始化一个无穷大的答案
        for k in range(0,len(nums1)):
            if nums1[k] == 0: 
                nums1[k] = 1 # 假设把第一个数组的0全部改成1
        k_ = sum(nums1) # 更新现在的值       
        o = min(o,o if j >= k_ or (k_-j)//j_ == 0 else k_) # 代入公式求解 这里不满足不要返回-1 而是原来的o
        for k in range(0,len(nums2)):
            if nums2[k] == 0:
                nums2[k] = 1 # 假设把第二个数组的0改成1
        k_ = sum(nums2) # 更新现在的和
        o = min(o,o if i >= k_ or (k_-i)//i_ == 0 else k_) # 代入公式求解 这里不满足不要返回-1 而是原来的o
        return o # 返回答案

示例代码

Python

# 时间复杂度O(n)
# 空间复杂度O(1) 仅用了若干变量
class Solution:
    def minSum(self, nums1: List[int], nums2: List[int]) -> int:
        i,j,i_,j_ = sum(nums1),sum(nums2),0,0
        for k in range(0,len(nums1)):
            if nums1[k] == 0:
                i_+=1 # 先统计第一个数组0的个数
        for k in range(0,len(nums2)):
            if nums2[k] == 0:
                j_+=1 # 然后是第二个数组0的个数
        if i == j and i_ == 0 and j_ == 0:
            return i # 如果值相等 第一个数组和第二个数组都没0 则返回任意一个数组的和
        if i_ == 0 and j_ == 0:
            return -1 if i != j else i # 如果第一个和第二个都没0 则判断一下他们的和
        if i_ == 0 and j_ != 0:
            return -1 if j >= i or (i-j)//j_ == 0 else i # 第一个数组有0 第二个数组没0 代入公式求解即可
        if i_ != 0 and j_ == 0:
            return -1 if i >= j or (j-i)//i_ == 0 else j # 第一个数组没0 第二个数组有0 代入公式求解即可
        o = 10 ** 11 # 初始化一个无穷大的答案
        for k in range(0,len(nums1)):
            if nums1[k] == 0: 
                nums1[k] = 1 # 假设把第一个数组的0全部改成1
        k_ = sum(nums1) # 更新现在的值       
        o = min(o,o if j >= k_ or (k_-j)//j_ == 0 else k_) # 代入公式求解 这里不满足不要返回-1 而是原来的o
        for k in range(0,len(nums2)):
            if nums2[k] == 0:
                nums2[k] = 1 # 假设把第二个数组的0改成1
        k_ = sum(nums2) # 更新现在的和
        o = min(o,o if i >= k_ or (k_-i)//i_ == 0 else k_) # 代入公式求解 这里不满足不要返回-1 而是原来的o
        return o # 返回答案

C++

// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution {
public:
    long long minSum(vector<int>& nums1, vector<int>& nums2) {
        long long i = 0; long long j = 0; int i_ = 0; int j_ = 0;
        for(int k = 0; k < nums1.size(); k++ ){
            if (nums1[k] == 0){i_++;}else{i+=nums1[k];}
        }
        for (int k = 0; k < nums2.size(); k++){
            if (nums2[k] == 0){j_++;}else{j+=nums2[k];}
        }
        if(i == j && i_ == 0 && j_ == 0){return i;}
        if(i_ == 0 && j_ == 0){return i = j ? -1 : i;}
        if(i_ == 0 && j_ != 0){return j >= i || (i-j)/j_ == 0 ? -1 : i;}
        if(i_ != 0 && j_ == 0){return i >= j || (j-i)/i_ == 0 ? -1 : j;}
        long long o = 100000000000;
        long long k_ = 0;
        for (int k = 0; k < nums1.size(); k++){
            if(nums1[k]==0){nums1[k] = 1;k_++;}else{k_+=nums1[k];}
        } 
        o = min(o,j >= k_ || (k_-j)/j_ == 0 ? o : k_);
        k_ = 0;
        for (int k = 0; k < nums2.size(); k++){
            if(nums2[k]==0){nums2[k] = 1; k_++;}else{k_+=nums2[k];}
        }
        o = min(o,i >= k_ || (k_-i)/i_ == 0 ? o : k_);
        if(o == 100000000000){return -1;}
        return o; 
    }
};

后记

这种题写起来真麻烦 博主测试的时候错了很多次

感谢你的收看