通过最少操作数使数组和相等【LC1775】
You are given two arrays of integers nums1 and nums2, possibly of different lengths. The values in the arrays are between 1 and 6, inclusive.
In one operation, you can change any integer’s value in any of the arrays to any value between 1 and 6, inclusive.
Return the minimum number of operations required to make the sum of values in nums1 equal to the sum of values in nums2. Return -1 if it is not possible to make the sum of the two arrays equal.
想正常收快递想出校或者就让我回家吧
就是说为什么我写的代码那么长…
- 思路：
。首先统计数组nums1和nums2的和sum1、sum2，如果sum1==sum2，那么直接返回0，否则需要判断是否能使数组nums1和nums2的和相等。如果可以，那么需要的最少操作数是多少？
。如何判断是否能使数组nums1和nums2的和相等？
假设sum1>sum2，div=sum1−sum2，我们应该尽最大可能减小sum1、并尽最大可能增大sum2。nums2如果数组nums1能够减小的最大数值+数组nums2能够增大的最大数值小于div，那么不可能使两个数组的和相等；反之，可以使两个数组的和相等
。如何获得最少操作数？
- 贪心的思想：
局部最优：一次操作尽最大可能减小div
全局最优：使用最少的操作数使div达到0
- 那么对于数组nums1我们应该从最大值max1开始减小，对于数组nums2我们应该从最小值min2开始增大，并且每次减小或者增大的值应该是允许范围内的最大值。【使用双指针定位】
- 如果max1−MIN_NUM>div，那么直接将max1减小至最小值MIN_NUM，此时div减小的值为max1−MIN_NUM；
- 如果MAX_NUM−min2>div，那么直接将min2扩大至最大值MAX_NUM，此时div`减小的值为MAX_NUM−min2；
- 如果max1−MIN_NUM<=div，那么只需要一次操作就可以将div变为0，此时将max1减小至最小值max1-div，此时div减小的值为div；
- 如果MAX_NUM−min2<=div，那么只需要一次操作就可以将div变为0，此时将min2扩大至最大值min2+div，此时div减小的值为div。
- 实现：
为了快速获得数组nums1和nums2的最大值和最小值，可以使用哈希表统计每个数字出现的次数map1、map2，倒序遍历map1获得max1，正序遍历map2获得min2【也可以将数组排序】
class Solution { int MAX_NUM = 6; int MIN_NUM = 1; public int minOperations(int[] nums1, int[] nums2) { int sum1 = 0; int sum2 = 0; int[] map1 = new int[MAX_NUM + 1]; int[] map2 = new int[MAX_NUM + 1]; // Arrays.sort(nums1); // Arrays.sort(nums2); for (int num1 :nums1){ sum1 += num1; map1[num1]++; } for (int num2 : nums2){ sum2 += num2; map2[num2]++; } // 不可能相等的情况 // nums1能够减小的数值 + nums2能够增大的数值 < dv if (sum1 > sum2){ if (isPossible(sum1, sum2, nums1.length, nums2.length, sum1 - sum2)){ return getMinOperations(map1, map2, sum1 - sum2); }else{ return -1; } }else if (sum1 < sum2 ){ if (isPossible(sum2, sum1, nums2.length, nums1.length, sum2 - sum1)){ return getMinOperations(map2, map1, sum2 - sum1); }else{ return -1; } } return 0; } public boolean isPossible (int sum1, int sum2, int len1, int len2, int dv){ // 不可能相等的情况 // nums1能够减小的数值 + nums2能够增大的数值 < dv int a = sum1 - len1 * MIN_NUM;// 全部减小至1 int b = len2 * MAX_NUM - sum2;//全部增大至6 return a + b >= dv; } // nums1和大于nums2 // 均为排序数组 public int getMinOperations(int[] map1, int[] map2, int dv){ int r = MAX_NUM; int l = MIN_NUM; int ans = 0; while (l < MAX_NUM || r > MIN_NUM){ // 如果dv >= r - MIN_NUM, 缩小至MIN_VALUE while (dv != 0 && dv > r - MIN_NUM && map1[r] > 0){ dv -= r - MIN_NUM; map1[r]--; map1[MIN_NUM]++; ans++; } // 如果dv <= MAX_NUM - 1, 扩大至MAX_VALUE while (dv != 0 && dv > MAX_NUM - l && map2[l] > 0 ){ dv -= MAX_NUM - l; map2[l]--; map2[MAX_NUM]++; ans++; } // 如果dv < r - MIN_NUM, 只需要一次操作就可以使dv变为0 while (dv != 0 && dv <= r - MIN_NUM && map1[r] > 0){ dv -= dv; map1[r]--; map1[r - dv]++; ans++; } // 如果dv < MAX_NUM - 1,, 只需要一次操作就可以使dv变为0 while (dv != 0 && dv <= MAX_NUM - l && map2[l] > 0 ){ dv -= dv; map2[l]--; map2[l + dv]++; ans++; } if (dv == 0){ break; } r--; l++; } return ans; } }
。复杂度
- 时间复杂度：O(n+m),n和m分别为数组nums1和nums2的长度
- 空间复杂度：O(C),C 为哈希表的空间
- 思路类似，不统计每个数字对应的个数，直接统计每个元素的最大变化量
class Solution { public int minOperations(int[] nums1, int[] nums2) { if (6 * nums1.length < nums2.length || 6 * nums2.length < nums1.length) return -1; // 优化 // int d = Arrays.stream(nums2).sum() - Arrays.stream(nums1).sum(); int d = 0; // 数组元素和的差，我们要让这个差变为 0 for (int x : nums2) d += x; for (int x : nums1) d -= x; if (d < 0) { d = -d; int[] tmp = nums1; nums1 = nums2; nums2 = tmp; // 交换，统一让 nums1 的数变大，nums2 的数变小 } int[] cnt = new int[6]; // 统计每个数的最大变化量 for (int x : nums1) ++cnt[6 - x]; // nums1 的变成 6 for (int x : nums2) ++cnt[x - 1]; // nums2 的变成 1 for (int i = 5, ans = 0; ; --i) { // 从大到小枚举最大变化量 5 4 3 2 1 if (i * cnt[i] >= d) // 可以让 d 变为 0 return ans + (d + i - 1) / i; ans += cnt[i]; // 需要所有最大变化量为 i 的数 d -= i * cnt[i]; } } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/equal-sum-arrays-with-minimum-number-of-operations/solutions/2009786/mei-xiang-ming-bai-yi-ge-dong-hua-miao-d-ocuu/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
