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

中等

82

相关企业

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

通过次数

9.5K

提交次数

17.8K

通过率

53.4%

题解：我的思路首先想到，什么情况下无法相等？当一个数组的最小值大于另一个数组的最大值的时候，就无法相等了。

另外问题，怎么确定一定可以相等？当两个数组sum的差值在两个数组可以调节的最大范围之内就一定可以相等。

那么调节的最大范围是多少呢？假设数组1的和大于数组2的和，那么数组1要减小，数组2要增加。减小的最大值是6->1 5->1 4->1 3->1 2->1;增加的最大值为1->6 2->6 3->6 4->6 5->6;于是很自然的想到了hashmap，统计每个数字出现的次数，能够计算出来调节的最大范围。

如果有解，那如何是最快的呢？想到找零问题，使用贪心法，按照5 4 3 2 1 进行调节即可。

以下是代码：

class Solution {
public:int minOperations(vector& nums1, vector& nums2) {int ret=0;int len1=nums1.size();int len2=nums2.size();if(len1sum2){// to doint diff=sum1-sum2;int charge[6]={0};charge[5]=count1[6]+count2[1];charge[4]=count1[5]+count2[2];charge[3]=count1[4]+count2[3];charge[2]=count1[3]+count2[4];charge[1]=count1[2]+count2[5];int chargeMax=5*charge[5]+4*charge[4]+3*charge[3]+2*charge[2]+charge[1];if(diff>chargeMax)return -1;int need5=diff/5;int yushu5=diff%5;if(need5<=charge[5]){diff=yushu5;ret+=need5;charge[4]+=(charge[5]-need5);}else{diff-=charge[5]*5;ret+=charge[5];}int need4=diff/4;int yushu4=diff%4;if(need4<=charge[4]){diff=yushu4;ret+=need4;charge[3]+=(charge[4]-need4);}else{diff-=charge[4]*4;ret+=charge[4];}int need3=diff/3;int yushu3=diff%3;if(need3<=charge[3]){diff=yushu3;ret+=need3;charge[2]+=(charge[3]-need3);}else{diff-=charge[3]*3;ret+=charge[3];}int need2=diff/2;int yushu2=diff%2;if(need2<=charge[2]){diff=yushu2;ret+=need2;charge[1]+=(charge[2]-need3);}else{diff-=charge[2]*2;ret+=charge[2];}ret+=diff;  // 最后只剩1了return ret;}else{int diff=sum2-sum1;int charge[6]={0};charge[5]=count2[6]+count1[1];charge[4]=count2[5]+count1[2];charge[3]=count2[4]+count1[3];charge[2]=count2[3]+count1[4];charge[1]=count2[2]+count1[5];int chargeMax=5*charge[5]+4*charge[4]+3*charge[3]+2*charge[2]+charge[1];if(diff>chargeMax)return -1;int need5=diff/5;int yushu5=diff%5;if(need5<=charge[5]){diff=yushu5;ret+=need5;charge[4]+=(charge[5]-need5);}else{diff-=charge[5]*5;ret+=charge[5];}int need4=diff/4;int yushu4=diff%4;if(need4<=charge[4]){diff=yushu4;ret+=need4;charge[3]+=(charge[4]-need4);}else{diff-=charge[4]*4;ret+=charge[4];}int need3=diff/3;int yushu3=diff%3;if(need3<=charge[3]){diff=yushu3;ret+=need3;charge[2]+=(charge[3]-need3);}else{diff-=charge[3]*3;ret+=charge[3];}int need2=diff/2;int yushu2=diff%2;if(need2<=charge[2]){diff=yushu2;ret+=need2;charge[1]+=(charge[2]-need3);}else{diff-=charge[2]*2;ret+=charge[2];}ret+=diff;  // 最后只剩1了return ret;}}
};

时间96 ms

击败

94.59%

内存111 MB

击败

91.89%