Leetcode 1775. 通过最少操作次数使数组的和相等

给你两个长度可能不等的整数数组 nums1 和 nums2 。两个数组中的所有值都在 1 到 6 之间（包含 1 和 6）。

每次操作中，你可以选择 任意 数组中的任意一个整数，将它变成 1 到 6 之间 任意 的值（包含 1 和 6）。

请你返回使 nums1 中所有数的和与 nums2 中所有数的和相等的最少操作次数。如果无法使两个数组的和相等，请返回 -1 。

 

示例 1：

输入：nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2]
输出：3
解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。
- 将 nums2[0] 变为 6 。 nums1 = [1,2,3,4,5,6], nums2 = [6,1,2,2,2,2] 。
- 将 nums1[5] 变为 1 。 nums1 = [1,2,3,4,5,1], nums2 = [6,1,2,2,2,2] 。
- 将 nums1[2] 变为 2 。 nums1 = [1,2,2,4,5,1], nums2 = [6,1,2,2,2,2] 。

示例 2：

输入：nums1 = [1,1,1,1,1,1,1], nums2 = [6]
输出：-1
解释：没有办法减少 nums1 的和或者增加 nums2 的和使二者相等。

示例 3：

输入：nums1 = [6,6], nums2 = [1]
输出：3
解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。
- 将 nums1[0] 变为 2 。 nums1 = [2,6], nums2 = [1] 。
- 将 nums1[1] 变为 2 。 nums1 = [2,2], nums2 = [1] 。
- 将 nums2[0] 变为 4 。 nums1 = [2,2], nums2 = [4] 。

 

提示：

    1 <= nums1.length, nums2.length <= 105
    1 <= nums1[i], nums2[i] <= 6


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

解法一：贪心 + 计数

我们首先应该从正反两个方向去分析，对于不合法的情况：只要两个数组一个全部变成6，一个全部变成1后仍然达不到要求，即变成6的数组和小于变成1的数组和，那么这种情况直接返回-1。


对于合法情况，一定能够使得两个数组的和相等，那么如何让总的操作次数最少呢？


我们用$sum1$和$sum2$分别代表$nums1$和$nums2$的和，这里不妨假设$sum1>sum2$。那么为了能使得两个数组的和相等，我们需要增加sum2的值，减少sum1的值，并且让操作次数尽可能少。为了使操作次数尽可能地少，很直观的一种想法就是尽可能每一次让增加或减少的数尽可能大。我们可以用$target$表示$sum1-sum2$,我们的目标是使$target$变为0。


为了使每一次增加的数尽可能大，减少的数尽可能小，我们首先让$nums1$中所有的$6$先减少，然后再让$nums2$中所有的$1$增加，接下来一次是5和2,…2和5，直至$target$变为0。


我们可以用哈希表来统计每次的增加量和减少量，对于$nums1$中的6每次减少量为5，$num2$中的1每次增加量为5，这些操作都会使得target减少，那么统计$nums1$中的6和$nums2$中的1保存再mp[5]中，代表每次target能够减少的次数。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

class Solution {
    int[] mp = new int[6];
    public int minOperations(int[] nums1, int[] nums2) {
        int n1 = nums1.length, n2 = nums2.length, ans = 0;
        if (n1 * 6 < n2 || n2 * 6 < n1) return -1; //一定不可行
        int target = Arrays.stream(nums1).sum() - Arrays.stream(nums2).sum(); //可行情况
        if (target < 0) return minOperations(nums2, nums1);//默认nums1为sum大的数组 
        for (int x : nums1) mp[x - 1]++; //对于每个数可以减少的量
        for (int x : nums2) mp[6 - x]++; //对于每个数可以增加的量 
        for (int i = 5; i >= 1 && target > 0; i--) {
            int cnt = Math.min(mp[i], (target + i - 1) / i); //最少需要的个数 +(i- 1)为了向上取整。
            ans += cnt;
            target -= cnt * i; //减去能够减少的最大值，若小于等等于0，代表已经使得两个数组相等
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:  
    int minOperations(vector<int>& nums1, vector<int>& nums2) {    
        int n1 = nums1.size(), n2 = nums2.size(), ans = 0;
        if (n1 * 6 < n2 || n2 * 6 < n1) return -1; //一定不可行
        int target = accumulate(nums1.begin(), nums1.end(), 0) - accumulate(nums2.begin(), nums2.end(), 0); //可行情况
        if (target < 0) return minOperations(nums2, nums1);//默认nums1为sum大的数组   
        vector<int> mp(6, 0);
        for (int x : nums1) mp[x - 1]++; //对于每个数可以减少的量
        for (int x : nums2) mp[6 - x]++; //对于每个数可以增加的量 
        for (int i = 5; i >= 1 && target > 0; i--) {
            int cnt = min(mp[i], (target + i - 1) / i); //最少需要的个数 +(i- 1)为了向上取整。
            ans += cnt;
            target -= cnt * i; //减去能够减少的最大值，若小于等等于0，代表已经使得两个数组相等
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

如果有问题,欢迎评论区交流, 如果有帮助到你，请给题解点个赞和收藏哈~~~