让数组不相等的最小总代价

You are given two 0-indexed integer arrays nums1 and nums2, of equal length n.

In one operation, you can swap the values of any two indices of nums1. The cost of this operation is the sum of the indices.

Find the minimum total cost of performing the given operation any number of times such that nums1[i] != nums2[i] for all 0 <= i <= n - 1 after performing all the operations.

Return the minimum total cost such that nums1 and nums2 satisfy the above condition. In case it is not possible, return -1.

 

Example 1:

Input: nums1 = [1,2,3,4,5], nums2 = [1,2,3,4,5]
Output: 10
Explanation: 
One of the ways we can perform the operations is:
- Swap values at indices 0 and 3, incurring cost = 0 + 3 = 3. Now, nums1 = [4,2,3,1,5]
- Swap values at indices 1 and 2, incurring cost = 1 + 2 = 3. Now, nums1 = [4,3,2,1,5].
- Swap values at indices 0 and 4, incurring cost = 0 + 4 = 4. Now, nums1 =[5,3,2,1,4].
We can see that for each index i, nums1[i] != nums2[i]. The cost required here is 10.
Note that there are other ways to swap values, but it can be proven that it is not possible to obtain a cost less than 10.

Example 2:

Input: nums1 = [2,2,2,1,3], nums2 = [1,2,2,3,3]
Output: 10
Explanation: 
One of the ways we can perform the operations is:
- Swap values at indices 2 and 3, incurring cost = 2 + 3 = 5. Now, nums1 = [2,2,1,2,3].
- Swap values at indices 1 and 4, incurring cost = 1 + 4 = 5. Now, nums1 = [2,3,1,2,2].
The total cost needed here is 10, which is the minimum possible.

Example 3:

Input: nums1 = [1,2,2], nums2 = [1,2,2]
Output: -1
Explanation: 
It can be shown that it is not possible to satisfy the given conditions irrespective of the number of operations we perform.
Hence, we return -1.

 

Constraints:

• n == nums1.length == nums2.length
• 1 <= n <= 105
• 1 <= nums1[i], nums2[i] <= n

/*
 * 思路：
 * 1. 首先检查 nums1 和 nums2 是否已经满足 nums1[i] != nums2[i] 对于所有的 i。
 * 2. 如果满足，总代价为 0。
 * 3. 否则，遍历 nums1 和 nums2，记录所有 nums1[i] == nums2[i] 的位置。
 * 4. 为了使 nums1 满足条件，交换 nums1 中这些相同元素的位置，
 *    尽量选择代价较小的交换方式。
 * 5. 如果无法通过交换满足条件，返回 -1。
 */

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class MinimumCostToSatisfyConditionStream {
    public int minCost(int[] nums1, int[] nums2) {
        int n = nums1.length;
        List<Integer> samePositions = IntStream.range(0, n)
                .filter(i -> nums1[i] == nums2[i])
                .boxed()
                .collect(Collectors.toList());

        if (samePositions.isEmpty()) {
            return 0;
        }

        samePositions.sort(Comparator.comparingInt(i -> nums1[i]));

        int totalCost = 0;
        Set<Integer> used = new HashSet<>();
        for (int pos : samePositions) {
            for (int i = 0; i < n; i++) {
                if (nums1[i] != nums2[i] && !used.contains(i)) {
                    totalCost += pos + i;
                    used.add(pos);
                    used.add(i);
                    int temp = nums1[pos];
                    nums1[pos] = nums1[i];
                    nums1[i] = temp;
                    break;
                }
            }
        }

        boolean valid = IntStream.range(0, n).allMatch(i -> nums1[i] != nums2[i]);

        return valid ? totalCost : -1;
    }

    public static void main(String[] args) {
        MinimumCostToSatisfyConditionStream solution = new MinimumCostToSatisfyConditionStream();
        int[] nums1 = {1, 2, 3, 4, 5};
        int[] nums2 = {1, 2, 3, 4, 5};
        System.out.println(solution.minCost(nums1, nums2)); // Output: 10
    }
}

此题解尝试通过统计在nums1和nums2中相同位置上的相同元素数量，来确定最少的交换次数。首先，初始化若干变量用于记录总的交换代价、需要交换的次数、最频繁元素的数量及其值。接着，遍历数组，对于每一对相同的元素，在nums1中统计其出现的次数，并更新如果这个元素出现的次数最多，则记录它作为mode。如果最终mode的两倍小于等于需要的交换次数，说明可以通过足够的交换避免所有冲突，返回计算的总代价；否则，如果mode元素太多，导致无法通过交换避免所有冲突，返回-1。

O(n)

O(n)