给你两个长度可能不等的整数数组 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 <= 1051 <= nums1[i], nums2[i] <= 6
贪心 + 计数排序。
设 s1, s2 分别表示数组 nums1, nums2 的和。不失一般性，可以设 s1 < s2。
直观上看，要想使得操作次数最小，我们应当尽可能增加 nums1 中元素的值，同时尽可能减少 nums2 中元素的值，因此：
- nums1 中每个元素 x 可以增加的量为
6-x ∈ [0,5] - nums2 中每个元素 x 可以减少的量为
x-1 ∈ [0,5]
记 diff = s2 - s1，我们要选出最少的元素，使得在 nums1 中元素的增加量与在 nums2 中元素的减少量之和大于等于 diff。因此我们可以贪心地从 5 这个增加/减少量开始递减地选取即可。
在实际的代码编写中，我们只需要使用一个长度为 6 的数组，其下标为增加 / 减少量，值为对应的元素数量。
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)
freq = [0] * 6
for x in nums1:
freq[6 - x] += 1
for x in nums2:
freq[x - 1] += 1
diff = s2 - s1
ans, i = 0, 5
while i > 0 and diff > 0:
while freq[i] and diff > 0:
diff -= i
freq[i] -= 1
ans += 1
i -= 1
return -1 if diff > 0 else ansclass Solution {
public int minOperations(int[] nums1, int[] nums2) {
int s1 = sum(nums1);
int s2 = sum(nums2);
if (s1 == s2) {
return 0;
}
if (s1 > s2) {
return minOperations(nums2, nums1);
}
int[] freq = new int[6];
for (int x : nums1) {
++freq[6 - x];
}
for (int x : nums2) {
++freq[x - 1];
}
int diff = s2 - s1;
int ans = 0;
for (int i = 5; i > 0 && diff > 0; --i) {
while (freq[i] > 0 && diff > 0) {
diff -= i;
--freq[i];
++ans;
}
}
return diff > 0 ? - 1 : ans;
}
private int sum(int[] nums) {
int s = 0;
for (int x : nums) {
s += x;
}
return s;
}
}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);
vector<int> freq(6);
for (int x : nums1) ++freq[6 - x];
for (int x : nums2) ++freq[x - 1];
int diff = s2 - s1;
int ans = 0;
for (int i = 5; i > 0 && diff > 0; --i)
{
while (freq[i] && diff > 0)
{
diff -= i;
--freq[i];
++ans;
}
}
return diff > 0 ? -1 : ans;
}
};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)
}
freq := make([]int, 6)
for _, x := range nums1 {
freq[6-x]++
}
for _, x := range nums2 {
freq[x-1]++
}
diff := s2 - s1
ans := 0
for i := 5; i > 0 && diff > 0; i-- {
for freq[i] > 0 && diff > 0 {
diff -= i
freq[i]--
ans++
}
}
if diff > 0 {
return -1
}
return ans
}
func sum(nums []int) int {
s := 0
for _, x := range nums {
s += x
}
return s
}