旺崽的博客

要么天赋异禀，要么天道酬勤

0%

LeetCode 5691 通过最少操作次数使数组的和相等

发表于 分类于 Valine：

题目链接

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

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

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

示例 1：

1
2
3
4
5
6
输入：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：

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

示例 3：

1
2
3
4
5
6
输入：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] 。

二分~

容易想到二分次数，但是 check 函数比较难想，我们要先计算两个数组和的差值 res，如果次数为 x，试想，我们必须要用 x 次操作使得两个数组的和尽可能接近，一次操作变化的最大值有下面两种情况：

  • 将数组和较大的数组 v1 按从大到小排序，变化的最大值即为 v1.front()-1
  • 将数组和较大的数组 v2 按从小到大排序，变化的最大值即为 6-v2.front()

基于上述的分类，我们可以开两个指针 l1,l2 指向两个数组的开头，在二分的过程中判断是否能让 res=0 即可，AC 代码如下：

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
41
42
43
44
45
46
47
class Solution {
public:
    bool check(int x, vector<int> &nums1, vector<int> &nums2, int res) {
        int l1 = 0, l2 = 0, cnt = 0;
        while (res > 0) {
            if (l1 < nums1.size() && l2 < nums2.size()) {
                if (nums1[l1] - 1 >= 6 - nums2[l2]) {
                    res -= nums1[l1] - 1;
                    l1++;
                    cnt++;
                } else {
                    res -= 6 - nums2[l2];
                    l2++;
                    cnt++;
                }
            } else if (l1 < nums1.size()) {
                res -= nums1[l1] - 1;
                l1++;
                cnt++;
            } else if (l2 < nums2.size()) {
                res -= 6 - nums2[l2];
                l2++;
                cnt++;
            } else break;
        }
        return (cnt <= x);
    }

    int minOperations(vector<int> &nums1, vector<int> &nums2) {
        int mn1 = nums1.size(), mx1 = nums1.size() * 6;
        int mn2 = nums2.size(), mx2 = nums2.size() * 6;
        int sum1 = accumulate(nums1.begin(), nums1.end(), 0);
        int sum2 = accumulate(nums2.begin(), nums2.end(), 0);
        if (sum1 < sum2) swap(nums1, nums2);
        sort(nums1.rbegin(), nums1.rend());
        sort(nums2.begin(), nums2.end());
        int res = abs(sum1 - sum2);
        if (mn2 > mx1 || mn1 > mx2) return -1;
        int l = 0, r = nums1.size() + nums2.size();
        while (l <= r) {
            int mid = l + r >> 1;
            if (check(mid, nums1, nums2, res)) r = mid - 1;
            else l = mid + 1;
        }
        return l;
    }
};