题目表述:
给你两个长度可能不等的整数数组 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的元素个数都取最大值6,仍然小于nums2的元素个数或者nums2的元素都取最大值6,依然小于nums1的元素个数。则直接返回-1;
剩下的情况都是可以满足最少操作的次数的案例。先计算出两个数组总和的差定义变为d,如果nums1的总和大于nums2,则d为< 0。用swap()函数将nums1数组赋值给nums2。nums2赋值给nums1。
数组的元素只可能是1、2、3、4、5、6。对于nums1来说,他的变化范围(往大变换)只能是5、4、3、2、1。对于nums2数组来说,变化范围(往小变换)只能是0、1、2、3、4、5。定义一个哈希数组,算出各个元素变量的个数。
对变量5、4、3、2、1.进行一次遍历。如果d大于变量*变量个数,返回的个数加上变量个数,d减去变量*变量个数。如果变量*变量个数大于等于d,将(d+变量-1)/变量,就是得到的操作数。break结束本次循环。返回所有的操作数相加。
ps:d+变量数-1 也就是取整,例如d=12 变化量=5.需要3次,就要17-1/5=3。减去1就是当d=15时,正好操作数为3,加上5再-1可以得到19,即操作数为3。
完整代码:
class Solution {
public:int minOperations(vector& nums1, vector& nums2) {int cnt1[7]{0};if(nums1.size()*60;i--){if(cnt1[i]*i>=d){int t=(d+i-1)/i;count=count+t;break;}else{count=count+cnt1[i];d=d-cnt1[i]*i;}}return count;}
};