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

题目描述

leetcode 中等题

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

提示1：

1 <= nums1.length, nums2.length <= 10^5
1 <= nums1[i], nums2[i] <= 6

贪心

设两个数组的和为 $sum1$ 、$sum2$，两者的差为 $diff$ 。

并且为了不失一般性，我们使 $nums1$ 的和始终是大于 $nums2$ 的。

因为需要通过最少次数使两个数组和相等，也就是使 $diff$ 尽快小于 $0$。那么为了更快的减少 $diff$ ，显然我们只能令 $nums1$ 中的某个数 $x$ 变成 $max(1, x - diff))$，这样一来 $x$ 对 $diff$ 贡献即为 $x - max(1, x - diff)$，同样为了更快的减少 $diff$ ，我们要尽可能的从更大贡献值的 $x$ 开始操作；对于 $num2$ 也同理，近似的改成相反操作即可。

class Solution {
    public int minOperations(int[] nums1, int[] nums2) {
        Map<Integer, Integer> count1 = Arrays.stream(nums1).boxed().collect(Collectors.toMap(Function.identity(), k -> 1, Integer::sum));
        Map<Integer, Integer> count2 = Arrays.stream(nums2).boxed().collect(Collectors.toMap(Function.identity(), k -> 1, Integer::sum));
        int diff = Arrays.stream(nums1).sum() - Arrays.stream(nums2).sum();
        if(diff < 0){
            // 为了统一, 让 count1 始终大于 count2
            diff = -diff;
            Map<Integer, Integer> tempMap = count1;
            count1 = count2;
            count2 = tempMap;
        }
        int ans = 0;
        while(diff > 0){
            int temp = ans;
            int max = count1.entrySet().stream().filter(e -> e.getValue() > 0).map(Map.Entry::getKey).mapToInt(Integer::valueOf).max().orElseThrow();
            int min = count2.entrySet().stream().filter(e -> e.getValue() > 0).map(Map.Entry::getKey).mapToInt(Integer::valueOf).min().orElseThrow();
            while(max - 1 >= 6 - min && diff > 0 && count1.getOrDefault(max, 0) > 0){
                int to = Math.max(1, max - diff);
                if(max == to){
                    break;
                }
                diff -= max - to;
                count1.compute(max, (key, old) -> --old);
                count1.compute(to, (key, old) -> old == null ? 1 : ++old);
                ans++;
                max = count1.entrySet().stream().filter(e -> e.getValue() > 0).map(Map.Entry::getKey).mapToInt(Integer::valueOf).max().orElseThrow();
            }
            while(max - 1 < 6 - min && diff > 0 && count2.getOrDefault(min, 0) > 0){
                int to = Math.min(6, min + diff);
                if(min == to){
                    break;
                }
                diff -= to - min;
                count2.compute(min, (key, old) -> --old);
                count2.compute(to, (key, old) -> old == null ? 1 : ++old);
                ans++;
                min = count2.entrySet().stream().filter(e -> e.getValue() > 0).map(Map.Entry::getKey).mapToInt(Integer::valueOf).min().orElseThrow();
            }
            if(ans == temp){
                return -1;
            }
        }
        return ans;
    }
}

哈希表优化

上面的解法代码过于复杂，我们可以通过哈希表来存储不同元素对于 $diff$ 的贡献，这样一来只需要从大到小遍历贡献值以减少 $diff$ 即可。

class Solution {
    public int minOperations(int[] nums1, int[] nums2) {
        Map<Integer, Integer> count1 = Arrays.stream(nums1).boxed().collect(Collectors.toMap(Function.identity(), k -> 1, Integer::sum));
        Map<Integer, Integer> count2 = Arrays.stream(nums2).boxed().collect(Collectors.toMap(Function.identity(), k -> 1, Integer::sum));
        int diff = Arrays.stream(nums1).sum() - Arrays.stream(nums2).sum();
        if(diff < 0){
            // 让 count1 始终大于 count2
            diff = -diff;
            Map<Integer, Integer> tempMap = count1;
            count1 = count2;
            count2 = tempMap;
        }
        int[] d = new int[7]; // 通过哈希表存储贡献值
        for(int i = 6; i >= 2; i--){
            d[i] += count1.getOrDefault(i, 0);
            d[i] += count2.getOrDefault(7 - i, 0);
        }
        int ans = 0;
        for(int i = 6; i >= 2 && diff > 0; i--){
            int curCount = Math.min(d[i], (diff + i - 2) / (i - 1)); // 后者是 diff / (i - 1) 的向上取整
            ans += curCount;
            diff -= curCount * (i - 1);
        }
        return diff <= 0 ? ans : -1;
    }
}