Medium

题目描述

给你一个下标从 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 <= 10^5
  • 1 <= nums[i] <= 10^6

解题思路

这道题的关键在于理解每种数字的频次如何通过删除操作清零。

首先统计每个数字的出现频次。如果某个数字只出现1次，那么无法清零（因为每次操作至少删除2个相同元素），直接返回-1。

对于频次大于1的数字，我们需要找到最少的操作次数组合。设某数字出现n次，我们可以用x次删除3个元素的操作和y次删除2个元素的操作，满足：3x + 2y = n。

关键观察：

  • 如果n能被3整除，用 n/3 次删除3个元素的操作最优
  • 如果n除以3余1，可以用1次删除2个元素的操作替换1次删除3个元素的操作（因为3+2=5，而2+2=4更少）
  • 如果n除以3余2，直接加1次删除2个元素的操作

因此，对于频次为n的数字，最少操作次数为：(n + 2) / 3（向上取整）

这个公式可以统一处理所有情况：

  • n % 3 == 0：操作次数为 n/3
  • n % 3 == 1：操作次数为 (n-1)/3 + 1 = (n+2)/3
  • n % 3 == 2：操作次数为 n/3 + 1 = (n+2)/3

最后将所有数字的最少操作次数相加即可。

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums) {
        unordered_map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }
        
        int operations = 0;
        for (auto& [num, freq] : count) {
            if (freq == 1) {
                return -1;
            }
            operations += (freq + 2) / 3;
        }
        
        return operations;
    }
};

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        from collections import Counter
        
        count = Counter(nums)
        operations = 0
        
        for freq in count.values():
            if freq == 1:
                return -1
            operations += (freq + 2) // 3
        
        return operations

public class Solution {
    public int MinOperations(int[] nums) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        
        foreach (int num in nums) {
            count[num] = count.GetValueOrDefault(num, 0) + 1;
        }
        
        int operations = 0;
        foreach (int freq in count.Values) {
            if (freq == 1) {
                return -1;
            }
            operations += (freq + 2) / 3;
        }
        
        return operations;
    }
}

var minOperations = function(nums) {
    const freq = {};
    for (const num of nums) {
        freq[num] = (freq[num] || 0) + 1;
    }
    
    let operations = 0;
    for (const count of Object.values(freq)) {
        if (count === 1) return -1;
        operations += Math.ceil(count / 3);
    }
    
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组统计频次，然后遍历哈希表计算操作次数
空间复杂度O(k)k为数组中不同元素的个数，用于存储哈希表