comments	difficulty	edit_url	rating	source	tags
true	中等	https://github.com/doocs/leetcode/edit/main/solution/1700-1799/1775.Equal%20Sum%20Arrays%20With%20Minimum%20Number%20of%20Operations/README.md	1850	第 230 场周赛 Q3	贪心 数组 哈希表 计数

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

English Version

题目描述

给你两个长度可能不等的整数数组 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

解法

方法一：贪心 + 排序

我们用 $s_1$ 和 $s_2$ 分别表示数组 nums1 和 nums2 的和。

如果 $s_1=s_2$，则不需要任何操作，直接返回 $0$。否则，我们不妨设 $s_1<s_2$，即 $num{s}_1$ 中的元素和小于 $num{s}_2$ 中的元素和，那么两个数组元素和的差值 $d=s_2-s_1$。

要使得两个数组元素和相等，我们需要对 nums1 中的元素进行增大操作，对 nums2 中的元素进行减小操作。

对于 nums1 中的每个元素 $v$，我们最多可以将其增大到 $6$，那么 $v$ 可以增大的量为 $6-v$。对于 nums2 中的每个元素 $v$，我们最多可以将其减小到 $1$，那么 $v$ 可以减小的量为 $v-1$。

我们将每个元素的变化量放入数组 arr 中，然后对数组 arr 进行降序排列。

接下来，我们从数组 arr 的第一个元素开始，贪心地将 $d$ 减去每个元素的变化量，直到 $d\le 0$，返回此时的操作次数即可。

遍历结束后，如果 $d>0$，说明无法使得两个数组元素和相等，返回 $-1$。

时间复杂度 $O((m+n)\times \log (m+n))$，空间复杂度 $O(m+n)$。其中 $m$ 和 $n$ 分别为数组 nums1 和 nums2 的长度。

Python3

class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
        s1, s2 = sum(nums1), sum(nums2)
        if s1 == s2:
            return 0
        if s1 > s2:
            return self.minOperations(nums2, nums1)
        arr = [6 - v for v in nums1] + [v - 1 for v in nums2]
        d = s2 - s1
        for i, v in enumerate(sorted(arr, reverse=True), 1):
            d -= v
            if d <= 0:
                return i
        return -1

Java

class Solution {
    public int minOperations(int[] nums1, int[] nums2) {
        int s1 = Arrays.stream(nums1).sum();
        int s2 = Arrays.stream(nums2).sum();
        if (s1 == s2) {
            return 0;
        }
        if (s1 > s2) {
            return minOperations(nums2, nums1);
        }
        int d = s2 - s1;
        int[] arr = new int[nums1.length + nums2.length];
        int k = 0;
        for (int v : nums1) {
            arr[k++] = 6 - v;
        }
        for (int v : nums2) {
            arr[k++] = v - 1;
        }
        Arrays.sort(arr);
        for (int i = 1, j = arr.length - 1; j >= 0; ++i, --j) {
            d -= arr[j];
            if (d <= 0) {
                return i;
            }
        }
        return -1;
    }
}

C++

class Solution {
public:
    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        int s1 = accumulate(nums1.begin(), nums1.end(), 0);
        int s2 = accumulate(nums2.begin(), nums2.end(), 0);
        if (s1 == s2) return 0;
        if (s1 > s2) return minOperations(nums2, nums1);
        int d = s2 - s1;
        int arr[nums1.size() + nums2.size()];
        int k = 0;
        for (int& v : nums1) arr[k++] = 6 - v;
        for (int& v : nums2) arr[k++] = v - 1;
        sort(arr, arr + k, greater<>());
        for (int i = 0; i < k; ++i) {
            d -= arr[i];
            if (d <= 0) return i + 1;
        }
        return -1;
    }
};

Go

func minOperations(nums1 []int, nums2 []int) int {
	s1, s2 := sum(nums1), sum(nums2)
	if s1 == s2 {
		return 0
	}
	if s1 > s2 {
		return minOperations(nums2, nums1)
	}
	d := s2 - s1
	arr := []int{}
	for _, v := range nums1 {
		arr = append(arr, 6-v)
	}
	for _, v := range nums2 {
		arr = append(arr, v-1)
	}
	sort.Sort(sort.Reverse(sort.IntSlice(arr)))
	for i, v := range arr {
		d -= v
		if d <= 0 {
			return i + 1
		}
	}
	return -1
}

func sum(nums []int) (s int) {
	for _, v := range nums {
		s += v
	}
	return
}

方法二：贪心 + 计数排序

方法一中，我们需要创建数组 arr 并进行排序，时空复杂度较高。由于数组 arr 中元素的范围为 $[0,..5]$，因此我们创建一个长度为 $6$ 的数组 cnt，用于统计数组 arr 中每个元素的数量，也即每个最大变化量的元素的数量。

接下来，我们从最大变化量 $i=5$ 开始，贪心地将 $d$ 减去最大变化量，直到 $d\le 0$，返回此时的操作次数即可。

时间复杂度 $O(m+n)$，空间复杂度 $O(C)$。其中 $m$ 和 $n$ 分别为数组 nums1 和 nums2 的长度。本题中 $C=6$。

Python3

class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
        s1, s2 = sum(nums1), sum(nums2)
        if s1 == s2:
            return 0
        if s1 > s2:
            return self.minOperations(nums2, nums1)
        cnt = Counter([6 - v for v in nums1] + [v - 1 for v in nums2])
        d = s2 - s1
        ans = 0
        for i in range(5, 0, -1):
            while cnt[i] and d > 0:
                d -= i
                cnt[i] -= 1
                ans += 1
        return ans if d <= 0 else -1

Java

class Solution {
    public int minOperations(int[] nums1, int[] nums2) {
        int s1 = Arrays.stream(nums1).sum();
        int s2 = Arrays.stream(nums2).sum();
        if (s1 == s2) {
            return 0;
        }
        if (s1 > s2) {
            return minOperations(nums2, nums1);
        }
        int d = s2 - s1;
        int[] cnt = new int[6];
        for (int v : nums1) {
            ++cnt[6 - v];
        }
        for (int v : nums2) {
            ++cnt[v - 1];
        }
        int ans = 0;
        for (int i = 5; i > 0; --i) {
            while (cnt[i] > 0 && d > 0) {
                d -= i;
                --cnt[i];
                ++ans;
            }
        }
        return d <= 0 ? ans : -1;
    }
}

C++

class Solution {
public:
    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        int s1 = accumulate(nums1.begin(), nums1.end(), 0);
        int s2 = accumulate(nums2.begin(), nums2.end(), 0);
        if (s1 == s2) return 0;
        if (s1 > s2) return minOperations(nums2, nums1);
        int d = s2 - s1;
        int cnt[6] = {0};
        for (int& v : nums1) ++cnt[6 - v];
        for (int& v : nums2) ++cnt[v - 1];
        int ans = 0;
        for (int i = 5; i; --i) {
            while (cnt[i] && d > 0) {
                d -= i;
                --cnt[i];
                ++ans;
            }
        }
        return d <= 0 ? ans : -1;
    }
};

Go

func minOperations(nums1 []int, nums2 []int) (ans int) {
	s1, s2 := sum(nums1), sum(nums2)
	if s1 == s2 {
		return 0
	}
	if s1 > s2 {
		return minOperations(nums2, nums1)
	}
	d := s2 - s1
	cnt := [6]int{}
	for _, v := range nums1 {
		cnt[6-v]++
	}
	for _, v := range nums2 {
		cnt[v-1]++
	}
	for i := 5; i > 0; i-- {
		for cnt[i] > 0 && d > 0 {
			d -= i
			cnt[i]--
			ans++
		}
	}
	if d <= 0 {
		return
	}
	return -1
}

func sum(nums []int) (s int) {
	for _, v := range nums {
		s += v
	}
	return
}