【大顶堆】个人练习-Leetcode-2170. Minimum Operations to Make the Array Alternating

题目链接：https://leetcode.cn/problems/minimum-operations-to-make-the-array-alternating/description/

题目大意：给一个数组nums[]，要求将其变为alternating数组，即其所有奇数下标的元素相等，所有偶数下标的元素相等，且奇数元素下标的元素不等于偶数下标的元素。

思路：很明显贪心就行，保留奇数下标元素中，出现次数第一大和第二大的元素及其次数（保留至第二大是因为要满足奇偶下标元素不等）。同样保留偶数下标元素中，出现次数第一大和第二大的元素及其次数。然后算一算总数减去两个第一大元素次数即可，如果碰见元素相等，就顺延至第二大。顺延奇数的还是偶数的都试一下。如果所有元素都相等（也就是没有第二大），那么就没法减，不用操作。

主要还是写起来比较麻烦，刚开始自己维护了个保留第一大和第二大的方法，虽然过了，但看着太丑陋了，就换成了用一个大顶堆来维护的方法。此外，考虑到数组只有一个元素的情况，特殊处理。这样就保证了其他情况下，奇数和偶数下标都至少有一个第一大元素。

此外，因为priority_queue对于pair的比较是从first开始的，我们在构建大顶堆时，将哈希表中的first, second要互换一下再放进堆中，因为这样才是让【出现次数】被用来比较。

完整代码

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        if (nums.size() == 1)
            return 0;
        unordered_map<int, int> a;
        unordered_map<int, int> b;
        priority_queue<pair<int, int>> ha;
        priority_queue<pair<int, int>> hb;

        for (int i = 0; i < nums.size(); i+=2)
            a[nums[i]]++;
        for (int i = 1; i < nums.size(); i+=2)
            b[nums[i]]++;
        
        for (auto it = a.begin(); it != a.end(); it++) 
            ha.emplace(make_pair(it->second, it->first));
        for (auto it = b.begin(); it != b.end(); it++) 
            hb.emplace(make_pair(it->second, it->first));

        auto a1 = ha.top();
        auto b1 = hb.top();
        ha.pop();
        hb.pop();
        int ans1 = nums.size() - a1.first;
        if (a1.second != b1.second) 
            ans1 -= b1.first;
        else {
            if (!hb.empty()) {
                ans1 -= hb.top().first;
            }
        }

        int ans2 = nums.size() - b1.first;
        if (a1.second != b1.second) 
            ans2 -= a1.first;
        else {
            if (!ha.empty()) {
                ans2 -= ha.top().first;
            }
        }
           
        return min(ans1, ans2);
    }
};