题目描述
给你一个下标从 0 开始的正整数数组 nums 。
你可以对数组执行以下两种操作 任意次 :
从数组中选择 两个 值 相等 的元素,并将它们从数组中 删除 。
从数组中选择 三个 值 相等 的元素,并将它们从数组中 删除 。
请你返回使数组为空的 最少 操作次数,如果无法达成,请返回 -1 。
样例
输入:nums = [2,3,3,2,2,4,2,3,4]
输出:4
解释:我们可以执行以下操作使数组为空:
- 对下标为 0 和 3 的元素执行第一种操作,得到 nums = [3,3,2,4,2,3,4] 。
- 对下标为 2 和 4 的元素执行第一种操作,得到 nums = [3,3,4,3,4] 。
- 对下标为 0 ,1 和 3 的元素执行第二种操作,得到 nums = [4,4] 。
- 对下标为 0 和 1 的元素执行第一种操作,得到 nums = [] 。
至少需要 4 步操作使数组为空。
输入:nums = [2,1,2,2,3,3]
输出:-1
解释:无法使数组为空。
范围
2 <= nums.length <= 105
1 <= nums[i] <= 106
用哈希表统计数组中每个数的个数。 当数组存在个数为1的数时,无法清空,返回-1; 从个数为2开始向后枚举,发现能被3整除,操作次数加上个数/3,否则,操作次数加上个数/3 + 1(直觉上来看优先删除三个值相同的数会使操作次数变少)。
C++ 代码
class Solution {
public:
int minOperations(vector<int>& nums) {
unordered_map<int,int> cnt;
for(auto& x : nums) cnt[x] ++;
for(auto& [k,v] : cnt)
if(v == 1) return -1;
int res = 0;
for(auto& [k,v] : cnt){
if(v % 3 == 0) res += v / 3;
else res += (v / 3 + 1);
}
return res;
}
};