美文网首页
1775. 通过最少操作次数使数组的和相等(难度:中等)

1775. 通过最少操作次数使数组的和相等(难度:中等)

作者: 一直流浪 | 来源:发表于2023-01-01 16:03 被阅读0次

    题目链接:https://leetcode.cn/problems/equal-sum-arrays-with-minimum-number-of-operations/

    题目描述:

    给你两个长度可能不等的整数数组 nums1nums2 。两个数组中的所有值都在 16 之间(包含 16)。

    每次操作中,你可以选择 任意 数组中的任意一个整数,将它变成 16 之间 任意 的值(包含 16)。

    请你返回使 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

    解法:贪心

    默认nums1的和小于nums2,若不满足则调换nums1nums2的元素。那么需要使两个数组的和相同,则需要增大nums1的元素值或者减小nums2的元素值。

    先分别计算nums1nums2元素和sum1和sum2,通过sum2 - sum1 得到两个数组相差的大小temp,通过数组 int[] dp[]表示每种影响大小对应的元素个数,nums[i] 的可影响大小是 6 - nums1[i],即nums1[i] 升到最大值6还可以波动的数值,nums2[i] 的可影响大小是 nums2[i] - 1,即nums2[i] 降到最小值1可波动的数值。

    使用贪心算法,依次从5,4,3,2,1的遍历 dp数组,减少temp直到6,使用result计算变换次数,得到结果。

    优化:

    当nums1元素全部变为6,nums2元素全部都变为1,但是nums1仍然小于nums2则可以直接返回-1。

    代码:

    class Solution {
        public int minOperations(int[] nums1, int[] nums2) {
            if (6 * nums1.length < nums2.length || 6 * nums2.length < nums1.length) {
                return -1;
            }
            int result = 0;
            int temp = 0;
            for (int i : nums2) {
                temp += i;
            }
            for (int i : nums1) {
                temp -= i;
            }
    
            if (temp < 0) {
                temp = -temp;
                int[] t = nums1;
                nums1 = nums2;
                nums2 = t;
            }
            
            int[] dp = new int[6];
            for (int i : nums1) {
                dp[6 - i]++;
            }
            for (int i : nums2) {
                dp[i - 1]++;
            }
    
            for (int i = 5; i > 0; i--) {
                if (temp > i * dp[i]) {
                    temp -= i * dp[i];
                    result += dp[i];
                } else {
                    return result + (int) Math.ceil(temp * 1.0 / i);
                }
            }
            return -1;
        }
    }
    

    相关文章

      网友评论

          本文标题:1775. 通过最少操作次数使数组的和相等(难度:中等)

          本文链接:https://www.haomeiwen.com/subject/modpqdtx.html