使数组中所有元素相等的最小操作数 II

You are given two integer arrays nums1 and nums2 of equal length n and an integer k. You can perform the following operation on nums1:

• Choose two indexes i and j and increment nums1[i] by k and decrement nums1[j] by k. In other words, nums1[i] = nums1[i] + k and nums1[j] = nums1[j] - k.

nums1 is said to be equal to nums2 if for all indices i such that 0 <= i < n, nums1[i] == nums2[i].

Return the minimum number of operations required to make nums1 equal to nums2. If it is impossible to make them equal, return -1.

 

Example 1:

Input: nums1 = [4,3,1,4], nums2 = [1,3,7,1], k = 3
Output: 2
Explanation: In 2 operations, we can transform nums1 to nums2.
1st operation: i = 2, j = 0. After applying the operation, nums1 = [1,3,4,4].
2nd operation: i = 2, j = 3. After applying the operation, nums1 = [1,3,7,1].
One can prove that it is impossible to make arrays equal in fewer operations.

Example 2:

Input: nums1 = [3,8,5,2], nums2 = [2,4,1,6], k = 1
Output: -1
Explanation: It can be proved that it is impossible to make the two arrays equal.

 

Constraints:

• n == nums1.length == nums2.length
• 2 <= n <= 105
• 0 <= nums1[i], nums2[j] <= 109
• 0 <= k <= 105

/*
 * 思路：
 * 使用Java Stream处理：
 * 1. 计算每个对应位置的差值。
 * 2. 分别统计增加和减少的总次数。
 * 3. 如果增加和减少的次数不等，则返回-1。
 * 4. 如果k为0，且所有差值都为0，则返回0，否则返回-1。
 * 5. 否则，返回总操作次数。总操作次数为增加或减少总次数的较大值（因为增加和减少应该相等）。
 */
import java.util.stream.IntStream;
public class Solution {
    public int minOperations(int[] nums1, int[] nums2, int k) {
        long[] counts = IntStream.range(0, nums1.length)
            .mapToLong(i -> nums1[i] - nums2[i])
            .filter(diff -> diff != 0)
            .map(diff -> diff > 0 ? diff / k : -diff / k)
            .toArray();
        long add = 0, subtract = 0;
        for (long count : counts) {
            if (count > 0) subtract += count;
            else add += -count;
        }
        return add == subtract ? (int)add : -1;
    }
}

题解的核心思想是首先计算两个数组中对应位置元素的差值，并检查这些差值是否能被k整除。若不能整除，则直接返回-1，因为不能通过指定操作使两数组相等。如果能整除，则计算每个位置需要的操作次数（差值除以k的商），并累加。特别地，对于所有正差值的累加总和（即需要增加的总次数），单独计算为变量ans。若总操作次数为0，说明两数组已相等，返回ans；否则返回-1。

O(n)

O(1)