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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都为 n 。

每次操作中，你可以选择交换 nums1 中任意两个下标处的值。操作的 开销 为两个下标的 和 。

你的目标是对于所有的 0 <= i <= n - 1 ，都满足 nums1[i] != nums2[i] ，你可以进行 任意次
操作，请你返回达到这个目标的 最小 总代价。

请你返回让 _ _nums1 和 nums2 _ _ 满足上述条件的 最小总代价 ，如果无法达成目标，返回 -1 。

示例 1：

**输入：** nums1 = [1,2,3,4,5], nums2 = [1,2,3,4,5]
**输出：** 10
**解释：**
实现目标的其中一种方法为：
- 交换下标为 0 和 3 的两个值，代价为 0 + 3 = 3 。现在 nums1 = [4,2,3,1,5] 。
- 交换下标为 1 和 2 的两个值，代价为 1 + 2 = 3 。现在 nums1 = [4,3,2,1,5] 。
- 交换下标为 0 和 4 的两个值，代价为 0 + 4 = 4 。现在 nums1 = [5,3,2,1,4] 。
最后，对于每个下标 i ，都有 nums1[i] != nums2[i] 。总代价为 10 。
还有别的交换值的方法，但是无法得到代价和小于 10 的方案。

示例 2：

**输入：** nums1 = [2,2,2,1,3], nums2 = [1,2,2,3,3]
**输出：** 10
**解释：**
实现目标的一种方法为：
- 交换下标为 2 和 3 的两个值，代价为 2 + 3 = 5 。现在 nums1 = [2,2,1,2,3] 。
- 交换下标为 1 和 4 的两个值，代价为 1 + 4 = 5 。现在 nums1 = [2,3,1,2,2] 。
总代价为 10 ，是所有方案中的最小代价。

示例 3：

**输入：** nums1 = [1,2,2], nums2 = [1,2,2]
**输出：** -1
**解释：**
不管怎么操作，都无法满足题目要求。
所以返回 -1 。

提示：

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

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场双周赛的看法~

统计满足 x=\textit{nums}_1[i]=\textit{nums}_2[i] 的数对的个数 swapCnt，以及 x 的众数 mode 及其出现次数 modeCnt。

分类讨论：

  • 如果 modeCnt 没有超过 swapCnt 的一半：
    • 如果 swapCnt 是偶数，那么两两交换即可；
    • 如果 swapCnt 是奇数，那么至少有三种不同的 x，其中一个数必然可以和 nums}_1[0] 交换；
    • 因此这种情况下，代价就是这些 x 的下标之和。
  • 如果 modeCnt 超过 swapCnt 的一半，或者说 modeCnt}\cdot 2 > \textit{swapCnt，根据鸽巢原理，无法通过重排这些数字，让数组不相等（因为还存在一些 mode 仍然相同）。这种情况必须不断寻找其他的满足 nums}_1[j]\ne\textit{nums}_2[j] 的数对，且数对中的数都不等于 mode，直到 modeCnt}\cdot 2 \le \textit{swapCnt 为止。为了让答案尽量小，应从左到右遍历数组。如果仍然无法满足要求，则返回 -1。
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:
        ans = swap_cnt = mode_cnt = mode = 0
        cnt = [0] * (len(nums1) + 1)
        for i, (x, y) in enumerate(zip(nums1, nums2)):
            if x == y:
                ans += i
                swap_cnt += 1
                cnt[x] += 1
                if cnt[x] > mode_cnt:
                    mode_cnt, mode = cnt[x], x

        for i, (x, y) in enumerate(zip(nums1, nums2)):
            if mode_cnt * 2 <= swap_cnt: break
            if x != y and x != mode and y != mode:
                ans += i
                swap_cnt += 1
        return ans if mode_cnt * 2 <= swap_cnt else -1
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public long minimumTotalCost(int[] nums1, int[] nums2) {
        long ans = 0L;
        int swapCnt = 0, modeCnt = 0, mode = 0, n = nums1.length;
        int[] cnt = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            int x = nums1[i];
            if (x == nums2[i]) {
                ans += i;
                ++swapCnt;
                ++cnt[x];
                if (cnt[x] > modeCnt) {
                    modeCnt = cnt[x];
                    mode = x;
                }
            }
        }

        for (int i = 0; i < n && modeCnt * 2 > swapCnt; ++i) {
            int x = nums1[i], y = nums2[i];
            if (x != y && x != mode && y != mode) {
                ans += i;
                ++swapCnt;
            }
        }
        return modeCnt * 2 > swapCnt ? -1 : ans;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    long long minimumTotalCost(vector<int> &nums1, vector<int> &nums2) {
        long ans = 0L;
        int swap_cnt = 0, mode_cnt = 0, mode, n = nums1.size(), cnt[n + 1];
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; ++i)
            if (int x = nums1[i]; x == nums2[i]) {
                ans += i;
                ++swap_cnt;
                ++cnt[x];
                if (cnt[x] > mode_cnt) {
                    mode_cnt = cnt[x];
                    mode = x;
                }
            }

        for (int i = 0; i < n && mode_cnt * 2 > swap_cnt; ++i) {
            int x = nums1[i], y = nums2[i];
            if (x != y && x != mode && y != mode) {
                ans += i;
                ++swap_cnt;
            }
        }
        return mode_cnt * 2 > swap_cnt ? -1 : ans;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func minimumTotalCost(nums1, nums2 []int) (ans int64) {
	var swapCnt, modeCnt, mode int
	cnt := make([]int, len(nums1)+1)
	for i, x := range nums1 {
		if x == nums2[i] {
			ans += int64(i)
			swapCnt++
			cnt[x]++
			if cnt[x] > modeCnt {
				modeCnt, mode = cnt[x], x
			}
		}
	}

	for i, x := range nums1 {
		if modeCnt*2 <= swapCnt {
			break
		}
		if x != nums2[i] && x != mode && nums2[i] != mode {
			ans += int64(i)
			swapCnt++
		}
	}
	if modeCnt*2 > swapCnt {
		return -1
	}
	return
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 nums}_1 的长度。
  • 空间复杂度：O(n)。还可以用摩尔投票算法做到 O(1)，见 169. 多数元素 。
 Comments
On this page
2499-让数组不相等的最小总代价