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

题目链接

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

题干

给你两个长度可能不等的整数数组 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 <= $10^5$
1 <= nums1[i], nums2[i] <= 6

分析：

代码：

class Solution {
public:
    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(),m = nums2.size();
        
        //特判 如果此时nums1和的最小值 都大于 nums2和的最大值 那么显然不能得出答案 反之也是一样
        if(n > 6*m || 6*n < m) return -1;

        int diff = accumulate(nums2.begin(),nums2.end(),0) - accumulate(nums1.begin(),nums1.end(),0);
        
        //保证 nums1是小的数组 nums2 是大的数组
        if(diff < 0){
            diff *= -1;
            swap(nums1,nums2);
        }

        //记录变化量
        int cnt[6] = {0};
        for(auto &x:nums1) cnt[6 - x]++;
        for(auto &x:nums2) cnt[x - 1]++;

        int ans = 0;
        //变化量从大到小枚举
        for(int i = 5;i >= 0;i--){
            //如果此时的变化量已经 超过 差值diff了 那么加上对其上取整的结果 退出循环
            if(i * cnt[i] >= diff){
                ans += (diff + i - 1)/i;
                break;
            }
            ans += cnt[i];
            diff -= cnt[i] * i;
        }
        return ans;
    }
};

时间复杂度：O(N)