2870.使数组为空的最少操作次数

本文主要是介绍2870.使数组为空的最少操作次数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给你一个下标从 0 开始的正整数数组 nums 。

你可以对数组执行以下两种操作 任意次 ：

• 从数组中选择 两个 值 相等 的元素，并将它们从数组中 删除 。
• 从数组中选择 三个 值 相等 的元素，并将它们从数组中 删除 。

请你返回使数组为空的 最少 操作次数，如果无法达成，请返回 -1 。

示例 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 步操作使数组为空。

示例 2：

输入：nums = [2,1,2,2,3,3]
输出：-1
解释：无法使数组为空。

提示：

• 2 <= nums.length <= 105
• 1 <= nums[i] <= 106

我们发现，如果数组中存在单一元素，即只出现一次的元素，那么就无法通过操作使得数组为空，通过哈希表来存储每个数出现的次数，次数n分为3种，第一种是3的倍数，只需要n/3次操作就可以把这个数从数组中删除；第二种是模3等于1的，这种我们肯定不能全部三个三个地删除，但是我们为了使用次数最少，那么应该尽量三个地删除，最后次数为（n-3-1）/3+（3+1）/2次，即（n-1）/3+1次；第三种是模3等于2的，只需要n/3+2/2=n/3+1次，第二种和第三种得到的答案是相同的，因此最终只有两种情况，分为是3的倍数和不是3的倍数

代码如下:

class Solution {public int minOperations(int[] nums) {HashMap<Integer,Integer>map = new HashMap<>();for(int num:nums){map.put(num,map.getOrDefault(num,0)+1);}int cnt = 0;for(int key:map.keySet()){if(map.get(key)==1){return -1;}else if(map.get(key)%3==1||map.get(key)%3==2){int m = map.get(key);cnt += (m/3+1);}else if(map.get(key)%3==0){int m = map.get(key);cnt += (m/3);}}return cnt;}
}

这篇关于2870.使数组为空的最少操作次数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---