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

2021-02-28

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

竞赛

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

1
2
3

输入：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

贪心算法

使用哈希表统计两个数组中每个数字出现的次数，并且分别计算两个数组中各个数字的和

首先判断两个数组中对消除两个数组和的差值diff的贡献最大的数字是哪一个，首先选则那个数字，如果选择的是和较大的那个数组中的数字，则用那个数字减去1即为贡献值contribute,如果选择的是和较小的那个数组中的数字，则用6减去那个数字即为贡献值contribute,使用一个计数值count统计需要操作的次数。

class Solution {

    public int minOperations(int[] nums1, int[] nums2) {
        int hash1[] = new int[7];
        int hash2[] = new int[7];

        int sum1 = 0;
        int sum2 = 0;

        int m = nums1.length;
        int n = nums2.length;

        if (m > 6 * n || n > 6 * m) return -1;

        for (int i = 0; i < m; i++) {
            hash1[nums1[i]]++;
            sum1 += nums1[i];
        }

        for (int i = 0; i < n; i++) {
            hash2[nums2[i]]++;
            sum2 += nums2[i];
        }

        if (sum1 == sum2) return 0;

        int diff = sum1 - sum2;
        int count = 0;
        if (diff > 0) {
            count = getMin(diff, hash2, hash1);
        } else {
            count = getMin(-diff, hash1, hash2);
        }

        return count;
    }

    public int getMin(int diff, int[] hash1, int[] hash2) {
        //sum2 大,从sum1补
        int count = 0;

        int index1 = 1;
        int index2 = 6;

        while (diff > 0 && index1 <= 6 && index2 >= 0) {

            int con1 = 6 - index1;
            int con2 = index2 - 1;

            if (con1 > con2) {
                if (diff - hash1[index1] * con1 <= 0) {
                    count += Math.ceil(diff * 1.0 / con1);
                    diff = 0;
                } else {
                    count += hash1[index1];
                    diff -= hash1[index1] * con1;
                }
                index1++;
            } else if (con1 < con2) {
                if (diff - hash2[index2] * con2 <= 0) {
                    count += Math.ceil(diff * 1.0 / con2);
                    diff = 0;
                } else {
                    count += hash2[index2];
                    diff -= hash2[index2] * con2;
                }
                index2--;
            } else {
                if (hash1[index1] > hash2[index2]) {
                    if (diff - hash1[index1] * con1 <= 0) {
                        count += Math.ceil(diff * 1.0 / con1);
                        diff = 0;
                    } else {
                        count += hash1[index1];
                        diff -= hash1[index1] * con1;
                    }
                    index1++;
                } else {
                    if (diff - hash2[index2] * con2 <= 0) {
                        count += Math.ceil(diff * 1.0 / con2);
                        diff = 0;
                    } else {
                        count += hash2[index2];
                        diff -= hash2[index2] * con2;
                    }
                    index2--;
                }
            }
        }
        while(diff>0&&index1<=6){
            int con1 = 6 - index1;
            if (diff - hash1[index1] * con1 <= 0) {
                count += Math.ceil(diff * 1.0 / con1);
                diff = 0;
            } else {
                count += hash1[index1];
                diff -= hash1[index1] * con1;
            }
            index1++;
        }
        while(diff>0&&index2>=0){
            int con2 = index2 - 1;
            if (diff - hash2[index2] * con2 <= 0) {
                count += Math.ceil(diff * 1.0 / con2);
                diff = 0;
            } else {
                count += hash2[index2];
                diff -= hash2[index2] * con2;
            }
            index2--;
        }

        return count;
    }


}