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

题目描述

这是 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 <= 10^5$
• $1 <= nums1[i], nums2[i] <= 6$

---

枚举 + 贪心 + 数学

令 nums1 的长度为 n，nums2 的长度为 m，根据题意两数组的值域分别为 $[n, 6n]$ 和 $[m, 6m]$，可分别视为数轴上的两条线段。

为了方便，我们人为固定 $n\leq m$，若不满足则交换两数组，返回 minOperations(nums2, nums1) 即可。

先来考虑无解的情况：当 $6n < m$ 时，说明两线段不重合，必然无法通过变换使得总和相等，直接返回 -1。

由于 $\max(n, m)$ 的范围为 $1e5$，且 $nums[i]$ 的值域大小 $C = 6$，因此我们可以通过枚举最终目标和 x（两线段的重合部分）来做，枚举范围不超过 $6 \times 1e5$。

于是问题转换为：对于一个原总和为 sum 的数组 nums 而言，按照题目的变换规则，至少经过多少次变换，才能将其总和变为 x。

根据原总和 sum 和目标结果 x 的大小关系进行分情况讨论（将两者差值绝对值记为 d）：

• 当 $sum < x$ 时，对于原数为 $nums[i]$ 的数而言，其能变为不超过 $nums[i] - 1$ 的任意数。

  例如 $6$ 能够变化为 $[1, 5]$ 中的任意数，即单个数值 $6$ 最多能够抵消 $6 - 1$ 个差值，不失一般性的可概括为原数为 $nums[i]$ 所能抵消的差值为 $nums[i] - 1$。

  因此，我们贪心的使用较大数进行变换（从 $6$ 往 $2$ 枚举 i），对于每个数值 i 而言，其所能提供的个数为 $\min(\left \lceil \frac{d}{i - 1} \right \rceil, cnst[i])$。

• 当 $sum > x$ 时，同理，原数为 $nums[i]$ 所能提供的最大抵消数为 $6 - nums[i]$，因此我们贪心使用较小数进行变换（从 $1$ 往 $5$ 枚举 i），对于每个数值 i 而言，其所能提供的个数为 $\min(\left \lceil \frac{d}{6 - i} \right \rceil, cnst[i])$。

如此一来，我们通过枚举两线段重合点 x，复杂度为 $O(C \times \max(n, m))$，并通过复杂度为 $O(C)$ 的数学方法来得知将两原数组总和变为 x 所需要的操作次数 cnt，在所有的 cnt 取最小值即是答案。整体计算量为 $3.6 \times 10^6$，可以过。

Java 代码：

class Solution {
    int[] c1 = new int[10], c2 = new int[10];
    int s1, s2;
    public int minOperations(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        if (n > m) return minOperations(nums2, nums1);
        if (m > 6 * n) return -1;
        for (int x : nums1) {
            c1[x]++; s1 += x;
        }
        for (int x : nums2) {
            c2[x]++; s2 += x;
        }
        int ans = n + m;
        for (int i = m; i <= 6 * n; i++) ans = Math.min(ans, getCnt(c1, s1, i) + getCnt(c2, s2, i));
        return ans;
    }
    int getCnt(int[] cnts, int sum, int x) {
        int ans = 0;
        if (sum > x) {
            for (int i = 6, d = sum - x; i >= 2 && d > 0; i--) {
                int c = Math.min((int) Math.ceil(d * 1.0 / (i - 1)), cnts[i]);
                ans += c; d -= c * (i - 1);
            }
        } else if (sum < x) {
            for (int i = 1, d = x - sum; i <= 5 && d > 0; i++) {
                int c = Math.min((int) Math.ceil(d * 1.0 / (6 - i)), cnts[i]);
                ans += c; d -= c * (6 - i);
            }
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int c1[10], c2[10];
    int s1, s2;
    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        if (n > m) return minOperations(nums2, nums1);
        if (m > 6 * n) return -1;
        for (int x : nums1) {
            c1[x]++; s1 += x;
        }
        for (int x : nums2) {
            c2[x]++; s2 += x;
        }
        int ans = n + m;
        for (int i = m; i <= 6 * n; i++) {
            ans = min(ans, getCnt(c1, s1, i) + getCnt(c2, s2, i));
        }
        return ans;
    }
    int getCnt(int cnts[], int sum, int x) {
        int ans = 0;
        if (sum > x) {
            for (int i = 6, d = sum - x; i >= 2 && d > 0; i--) {
                int c = min((int) ceil(d * 1.0 / (i - 1)), cnts[i]);
                ans += c; d -= c * (i - 1);
            }
        } else if (sum < x) {
            for (int i = 1, d = x - sum; i <= 5 && d > 0; i++) {
                int c = min((int) ceil(d * 1.0 / (6 - i)), cnts[i]);
                ans += c; d -= c * (6 - i);
            }
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
        n, m = len(nums1), len(nums2)
        if n > m:
            return self.minOperations(nums2, nums1)
        if m > 6 * n:
            return -1
        c1, c2 = Counter(nums1), Counter(nums2)
        s1, s2 = sum(nums1), sum(nums2)
        def getCnt(cnts, tot, x):
            ans = 0
            if tot > x:
                d = tot - x
                for i in range(6, 1, -1):
                    if d <= 0:
                        break
                    c = min(math.ceil(d / (i - 1)), cnts[i])
                    ans, d = ans + c, d - c * (i - 1)
            elif tot < x:
                d = x - tot
                for i in range(1, 6):
                    if d <= 0:
                        break
                    c = min(math.ceil(d / (6 - i)), cnts[i])
                    ans, d = ans + c, d - c * (6 - i)
            return ans
        ans = n + m
        for i in range(m, 6 * n + 1):
            ans = min(ans, getCnt(c1, s1, i) + getCnt(c2, s2, i))
        return ans

• 时间复杂度：$O(C \times \max(n, m) \times C)$，其中 $C = 6$ 为 $nums[i]$ 的值域大小
• 空间复杂度：$O(C)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1775 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。