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

## 问题描述
[2170. 使数组变成交替数组的最少操作数 (Medium)](https://leetcode.cn/problems/minimum-operations-to-make-the-array-alternating/)

给你一个下标从 **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⁵`

## 解题思路
贪心，分别记录`nums`的奇数索引的元素中出现最多的两个元素及其出现次数，记为`max_2, max_num2, second_2, second_num2`，以及`nums`的偶数索引的元素中出现最多的两个元素及其出现次数，记为`max_1, max_num1, second_1, second_num1`，如果`max_1 != max_2`，结果`res`为`nums.size() - max_num1 - max_num2`，否则`res = std::min(nums.size() - max_num1 - second_num2, nums.size() - second_num1 - max_num2)`。

## 代码
```cpp
class Solution {
  public:
    // map，内部元素为pair<int, int> 数字以及数字出现个数
    int minimumOperations(vector<int> &nums) {
        auto cmp = [&](pair<int, int> &p1, pair<int, int> &p2) {
            return p1.second < p2.second;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq1(cmp);
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq2(cmp);
        unordered_map<int, int> mp1, mp2;
        for (int i = 0; i < nums.size(); i += 2) {
            mp1[nums[i]]++;
            if (i + 1 < nums.size()) {
                mp2[nums[i + 1]]++;
            }
        }
        int max_1 = 0, second_1 = 0;
        int max_num1 = 0, second_num1 = 0;
        int max_2 = 0, second_2 = 0;
        int max_num2 = 0, second_num2 = 0;
        for (auto &p1 : mp1) {
            if (p1.second >= max_1) {
                second_1 = max_1;
                second_num1 = max_num1;
                max_1 = p1.second;
                max_num1 = p1.first;
            } else if (p1.second >= second_1) {
                second_1 = p1.second;
                second_num1 = p1.first;
            }
        }
        for (auto &p2 : mp2) {
            if (p2.second >= max_2) {
                second_2 = max_2;
                second_num2 = max_num2;
                max_2 = p2.second;
                max_num2 = p2.first;
            } else if (p2.second >= second_2) {
                second_2 = p2.second;
                second_num2 = p2.first;
            }
        }
        if (max_num1 != max_num2) {
            return nums.size() - max_1 - max_2;
        }
        return std::min(nums.size() - max_1 - second_2, nums.size() - max_2 - second_1);
    }
};
```