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

标签: 贪心 数组 哈希表 计数

难度: 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 <= 105
  • 1 <= nums[i] <= 106

Submission

运行时间: 64 ms

内存: 32.8 MB

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

Explain

这个题解首先使用了Counter类来计算数组中每个数字出现的次数。然后检查如果某个数字的出现次数为1，直接返回-1，因为单个数字无法通过题目给定的操作被删除。如果所有数字的出现次数都不为1，接下来计算最小操作次数：对于每个数字出现的次数c，使用公式(c+2)//3来计算至少需要多少次操作可以删除这些数字。这个公式是基于尽可能多地使用三个相同元素的删除操作，因为这种操作对于减少总操作次数最为有效。最后，将所有数字的操作次数相加得到结果。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        from collections import Counter
        # 计算nums中每个元素的出现次数
        counts = Counter(nums)
        # 如果任何元素出现次数为1，则无法通过题目操作使数组为空
        if 1 in counts.values():
            return -1
        # 计算使数组为空的最少操作次数
        return sum((c+2) // 3 for c in counts.values())

Explore

在题目的约定中，若要删除数组中的元素，必须至少有三个相同的元素一起删除，或者两个相同的元素配合一个其他元素删除。因此，如果某个元素在数组中只出现了一次，根据题目的删除规则，无法找到有效的操作将这个单独的元素删除，因为它既不能单独形成一组也无法与其他两个元素组合删除（因为它是唯一的）。因此，如果任何元素的出现次数为1，则整个数组无法被完全清空，返回-1是符合逻辑的。

该公式`(c+2) // 3`是基于每次最优删除操作（即每次尽可能删除三个相同的元素）得来的。通过向c（元素的出现次数）加2再整除3的方式，可以确保涵盖所有可能的最后余下的元素情况（例如余下1个或2个）。这个公式适用于c不为1的所有情况。其基本思想是通过最大化每次删除三个相同元素的次数来最小化总操作次数。对于c大于等于3的情况，这个公式非常有效。

对于出现次数恰好为2的数字，根据题解中使用的公式`(c+2) // 3`，计算得`(2+2) // 3 = 4 // 3 = 1`。这表明，尽管数字只出现了2次，但我们可以通过一次操作将它们删除，这需要和另一个不同的元素一起进行删除（即一次操作删除两个相同的和一个不同的元素）。因此，这种情况被有效地处理了，使得数组向着空集的方向进一步。

在大多数情况下，尽可能使用三个相同元素的删除操作是最优的策略，因为它最大化了每次操作删除的元素数量，从而减少了总的操作次数。然而，这种策略假设了其他元素的出现次数也足以支持这种删除模式。在某些特殊情况下（如元素分布极不均匀时），可能需要更灵活地调整删除策略，以考虑两个相同元素配合一个其他元素的删除情况。因此，尽管这是一个高效的通用策略，但在一些边缘情况下可能需要调整。