问题描述
2170. 使数组变成交替数组的最少操作数 (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⁵
解题思路
贪心,分别记录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)
。
代码
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);
}
};
标签:操作数,num1,num2,nums,max,second,2170,数组
From: https://www.cnblogs.com/zwyyy456/p/17478101.html