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

难度: Medium

给你一个下标从 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 <= 10⁵
1 <= nums[i] <= 10⁵

Submission

运行时间: 103 ms

内存: 29.7 MB

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0
        even = nums[::2]
        odd = nums[1::2]
        even = collections.Counter(even).most_common(2)
        odd = collections.Counter(odd).most_common(2)
        if even[0][0] != odd[0][0]:
            return n - even[0][1] - odd[0][1]
        if len(even) == 1:
            even.append((0, 0))
        if len(odd) == 1:
            odd.append((0, 0))
        return min(n - even[0][1] - odd[1][1], n - even[1][1] - odd[0][1])

Explain

此题解的思路是将原数组分成两个子数组，一个包含所有偶数索引的元素，另一个包含所有奇数索引的元素。然后分别统计这两个子数组中元素的出现频率，并找出出现频率最高的两个元素（如果存在的话）。主要的考虑是：1. 最频繁出现在偶数索引位置的元素和最频繁出现在奇数索引位置的元素不相同时，我们只需要将其他元素更改为这两个元素即可。2. 如果两者相同，则需要考虑第二频繁的元素，以确保交替模式的成立。这涉及到比较更改后的总成本，选择最小的操作数。

时间复杂度: O(n)

空间复杂度: O(n)

import collections
from typing import List

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0  # 如果数组只有一个元素，无需操作
        even = nums[::2]  # 提取偶数索引的元素
        odd = nums[1::2]  # 提取奇数索引的元素
        even = collections.Counter(even).most_common(2)  # 统计偶数索引元素的频率
        odd = collections.Counter(odd).most_common(2)  # 统计奇数索引元素的频率
        if even[0][0] != odd[0][0]:
            return n - even[0][1] - odd[0][1]  # 如果最频繁的元素不同，则返回需要的最小操作数
        if len(even) == 1:
            even.append((0, 0))  # 如果偶数数组中只有一个元素类型，添加一个虚拟元素
        if len(odd) == 1:
            odd.append((0, 0))  # 如果奇数数组中只有一个元素类型，添加一个虚拟元素
        return min(n - even[0][1] - odd[1][1], n - even[1][1] - odd[0][1])  # 选择最小的操作数以满足交替数组的条件

Explore

在处理偶数和奇数索引的子数组时，选择出现频率最高的两个元素是为了最大限度减少需要进行的更改次数。目标是使数组在偶数位置和奇数位置上的元素交替出现。如果我们选择频率最高的元素作为目标元素，那么需要更改的元素数量会最少。如果最频繁的元素在偶数和奇数索引中相同，我们需要考虑第二频繁的元素来确保可以形成交替模式，这就是为什么需要考虑两个最频繁的元素。

当偶数索引和奇数索引的最频繁元素相同时，直接使用这两个元素会导致所有偶数位置和所有奇数位置上的元素都一样，无法形成交替模式。因此，我们必须选择一个不同的元素作为其中一个位置的目标元素。通过计算更改偶数索引最频繁元素和奇数索引第二频繁元素（或者相反）所需的操作数，可以找到需要最小更改次数的方案。这两种方案的最小值即为所需的最少操作数，确保数组能成功转换成交替数组。

如果偶数和奇数索引的数组中存在多种元素出现频率相同且最高，算法将从这些元素中选择任意一个作为最频繁的元素。如果这些元素之间可以形成交替模式，即它们在偶数位置和奇数位置互不相同，则直接选择其中的任意组合。如果这些最高频率的元素相同，则会进一步考虑次频繁的元素，以确保可以形成有效的交替模式。因此，算法可以灵活应对多个最高频率元素的情况，选择使更改操作最小化的组合。

在长度为1的数组中直接返回0是因为单个元素的数组本身已经符合交替数组的定义，因为不存在相邻元素。所以，无需进行任何操作就已经是交替数组。在这种情况下，不存在其他的操作需求或可能性，因为任何更改都是不必要的。