美化数组的最少删除数

难度: Medium

给你一个下标从 0 开始的整数数组 nums ，如果满足下述条件，则认为数组 nums 是一个 美丽数组 ：

nums.length 为偶数
对所有满足 i % 2 == 0 的下标 i ，nums[i] != nums[i + 1] 均成立

注意，空数组同样认为是美丽数组。

你可以从 nums 中删除任意数量的元素。当你删除一个元素时，被删除元素右侧的所有元素将会向左移动一个单位以填补空缺，而左侧的元素将会保持不变。

返回使 nums 变为美丽数组所需删除的最少元素数目。

示例 1：

输入：nums = [1,1,2,3,5]
输出：1
解释：可以删除 nums[0] 或 nums[1] ，这样得到的 nums = [1,2,3,5] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 1 个元素。

示例 2：

输入：nums = [1,1,2,2,3,3]
输出：2
解释：可以删除 nums[0] 和 nums[5] ，这样得到的 nums = [1,2,2,3] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 2 个元素。

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵

Submission

运行时间: 70 ms

内存: 27.3 MB

class Solution:
    def minDeletion(self, nums: List[int]) -> int:
        ans = 0
        left = -1
        for x in nums:
            if left == -1:
                left = x
            elif x != left:
                left = -1
            else:
                ans += 1
        return ans + int(left >= 0)

Explain

本题解采用了一个一遍扫描的方法。首先定义一个变量left来记录当前正在处理的一对数中的第一个数。遍历数组nums，如果left为-1，表示当前没有悬挂的数，将当前数x赋值给left。如果left不为-1且x不等于left，表示当前数与上一个数不相等，可以组成一对有效的数，于是将left重置为-1。如果x等于left，表示与上一个数相等，需要删除当前这个数，删除计数ans增加1。最后，如果数组处理完后left仍有值（即数组长度为奇数），需要额外删除一个元素以保证数组长度为偶数，这时ans再加1。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minDeletion(self, nums: List[int]) -> int:
        ans = 0  # 初始化删除元素的计数器
        left = -1  # 初始化左侧元素，-1表示无当前悬挂的元素
        for x in nums:  # 遍历数组中的每个元素
            if left == -1:  # 如果没有悬挂元素，接受当前元素作为左侧元素
                left = x
            elif x != left:  # 如果当前元素与左侧元素不同，它们构成一对有效的美丽数组元素
                left = -1  # 重置左侧元素
            else:  # 如果当前元素与左侧元素相同，需要删除当前元素
                ans += 1  # 增加删除计数
        return ans + int(left >= 0)  # 如果数组处理完毕后left仍然存有值，需要额外删除，确保数组长度为偶数

Explore

在算法中使用`left`初始化为-1而不是使用布尔变量，是为了同时记录是否有悬挂的元素以及该元素的值。这种做法减少了额外的变量使用，简化了代码的逻辑。如果使用布尔变量，还需要另一个变量来存储悬挂的元素值，这会使代码复杂度略微增加。

在输入如[1,1,1,2]的情况下，算法会首先将第一个1设置为`left`，遇到第二个1时，由于它与`left`相同，因此将其删除并增加删除计数。接着第三个1再次与新的`left`（即第一个1）比较，同样进行删除。直到遇到2，由于与`left`不同，会重置`left`为-1。这种方式确保了连续相同元素超过两个时，除第一个外的所有相同元素都会被删除。

算法通过`int(left >= 0)`确保如果处理结束后`left`中仍有元素（即数组为奇数长度时），会进行额外删除以确保数组长度为偶数。这种方法在大多数情况下有效，但如果最后一个元素已经被考虑进删除计数（例如在一对有效的数中作为第二个数），则不需要额外删除。因此，这种方法在特定情况下可能会导致删除次数比最少需要的次数多1，需要根据具体实现和题目要求进行调整。

算法的目标是计算最少的删除次数以使数组中任意相邻的元素都不相同，而不是实际构建这样的数组。因此，通过重置`left`来跳过已构成有效对的元素是符合题目要求的。这种处理方法可以有效地减少需要处理的数据量，从而快速确定最少的删除次数，达到题目的要求。