博客

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

思路

• 先处理极端情况：
  • 若
    
nums1

    的中所有元素都是6，但是其和小于
    
nums2

    的长度，直接返回
    
-1

    ,因为这种情况一定不会成功。
  • 同理若
    
nums2

    的中所有元素都是6，但是其和小于
    
nums1

    的长度，直接返回
    
-1

    ,因为这种情况一定不会成功。
• 若想两个数组的和相等，则和大的数组的和一定会变小，和小的数组的和一定会变大。所以维护一个长度为
  
6

  数组
  
countDistance

  ，其中
  
countDistance[i]

  表示距离为i出现的次数(其中大的数组一定会减小，所以
  
i

  为
  
(6 - num)

  , 小的数组一定会增大，所以
  
i

  为
  
(num - 1)

  )。
• 由于要求计算出最小操作次数，所以我们需要从
  
countDistance

  数组末尾开始遍历执行对比操作,
  
distance <= i

  时直接返回结果。

CODE

class Solution {
    public int minOperations(int[] nums1, int[] nums2) {
        int N = nums1.length;
        int M = nums2.length;
        int sum1 = Arrays.stream(nums1).sum();
        int sum2 = Arrays.stream(nums2).sum();

        if (6 * N < M || 6 * M < N) {
            return -1;
        }

        if (sum1 == sum2) {
            return 0;
        }

        int[] countDistance = new int[6];
        if (sum1 > sum2) {
            for (int num : nums1) {
                countDistance[num - 1] = countDistance[num - 1] + 1;
            }
            for (int num : nums2) {
                countDistance[6 - num] = countDistance[6 - num] + 1;
            }
        } else {
            for (int num : nums2) {
                countDistance[num - 1] = countDistance[num - 1] + 1;
            }
            for (int num : nums1) {
                countDistance[6 - num] = countDistance[6 - num] + 1;
            }
        }
        int distance = sum1 > sum2 ? sum1 - sum2 : sum2 - sum1;
        int res = 0;
        for (int i = 5; i >= 0; i--) {
            while (countDistance[i] > 0) {
                res++;
                countDistance[i] = countDistance[i] - 1;
                if (distance <= i) {
                    return res;
                }
                distance = distance - i;
            }
        }
        return -1;
    }
}

参考题解