2170-使数组变成交替数组的最少操作数

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

给你一个下标从 0 开始的数组 nums ，该数组由 n 个正整数组成。

如果满足下述条件，则数组 nums 是一个 交替数组 ：

  • nums[i - 2] == nums[i] ，其中 2 <= i <= n - 1 。
  • nums[i - 1] != nums[i] ，其中 1 <= i <= n - 1 。

在一步 操作 中，你可以选择下标 i 并将 nums[i] 更改 为 任一 正整数。

返回使数组变成交替数组的 最少操作数 。

示例 1：

**输入：** nums = [3,1,3,2,4,3]
**输出：** 3
**解释：**
使数组变成交替数组的方法之一是将该数组转换为 [3,1,3, _ **1**_ , _ **3**_ , _ **1**_ ] 。
在这种情况下，操作数为 3 。
可以证明，操作数少于 3 的情况下，无法使数组变成交替数组。

示例 2：

**输入：** nums = [1,2,2,2,2]
**输出：** 2
**解释：**
使数组变成交替数组的方法之一是将该数组转换为 [1,2, _ **1**_ ,2, _ **1**_ ].
在这种情况下，操作数为 2 。
注意，数组不能转换成 [ _ **2**_ ,2,2,2,2] 。因为在这种情况下，nums[0] == nums[1]，不满足交替数组的条件。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

方法一：选择奇偶下标出现次数最多的数

思路与算法

根据题目的要求，我们最后需要将数组变为如下形式：

  • 所有奇数下标的元素均相同；

  • 所有偶数下标的元素均相同；

  • 奇数下标的元素和偶数下标的元素不能相同。

由于我们希望操作次数尽可能少，因此我们可以对奇数下标的元素和偶数下标的元素分别建立一个哈希映射，其中键表示某一个元素，值表示该元素出现的次数。这样一来，我们贪心地选择两个哈希映射中值最大的两个键，将所有奇数下标的元素变为奇数哈希映射对应的键，偶数下标的元素变为偶数哈希映射对应的键即可。如果两个键对应的值分别为 x 和 y，那么需要修改的次数即为：

n - x - y

但这样做并不能保证「奇数下标的元素和偶数下标的元素不能相同」。如果两个键表示的元素不相同，那么上述方法就是正确的，但如果两个键表示的元素相同，那么最终数组并不满足题目要求。因此除了值最大的键以外，我们还需要筛选出值次大的键。如果两个最大键表示的元素相同，那么一个最大键和另一个次大键表示的元素一定不相同，因此修改次数即为「奇数哈希映射最大键对应的值」加上「偶数哈希映射次大键对应的值」与「奇数哈希映射次大键对应的值」加上「偶数哈希映射最大键对应的值」二者中的较大值，再用 n 减去该值。

代码

[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
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int n = nums.size();

        // start = 0 表示偶数下标，start = 1 表示奇数下标
        // 返回值为最大键，最大键对应的值，次大键，次大键对应的值
        auto get = [&](int start) -> tuple<int, int, int, int> {
            unordered_map<int, int> freq;
            for (int i = start; i < n; i += 2) {
                ++freq[nums[i]];
            }

            int fstkey = 0, fstval = 0, sndkey = 0, sndval = 0;
            for (const auto& [key, val]: freq) {
                if (val > fstval) {
                    tie(sndkey, sndval) = tuple{fstkey, fstval};
                    tie(fstkey, fstval) = tuple{key, val};
                }
                else if (val > sndval) {
                    tie(sndkey, sndval) = tuple{key, val};
                }
            }

            return {fstkey, fstval, sndkey, sndval};
        };

        auto [e1stkey, e1stval, e2ndkey, e2ndval] = get(0);
        auto [o1stkey, o1stval, o2ndkey, o2ndval] = get(1);

        if (e1stkey != o1stkey) {
            return n - (e1stval + o1stval);
        }
        
        return n - max(e1stval + o2ndval, o1stval + e2ndval);
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        n = len(nums)
        
        # start = 0 表示偶数下标，start = 1 表示奇数下标
        # 返回值为最大键，最大键对应的值，次大键，次大键对应的值
        def get(start: int) -> Tuple[int, int, int, int]:
            freq = Counter(nums[start::2])
            best = freq.most_common(2)
            if not best:
                return 0, 0, 0, 0
            if len(best) == 1:
                return *best[0], 0, 0
            
            return *best[0], *best[1]
            
        e1stkey, e1stval, e2ndkey, e2ndval = get(0)
        o1stkey, o1stval, o2ndkey, o2ndval = get(1)

        if e1stkey != o1stkey:
            return n - (e1stval + o1stval)
        
        return n - max(e1stval + o2ndval, o1stval + e2ndval)

复杂度分析

  • 时间复杂度：O(n)。

  • 空间复杂度：O(n)，即为哈希表需要使用的空间。

 Comments
On this page
2170-使数组变成交替数组的最少操作数