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] 是一个美丽数组。可以证明你需要至少 1 次删除操作才能使 nums 变为美丽数组。

示例 2：

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

提示：

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^5

解题思路

这道题的核心在于理解美丽数组的定义：数组长度必须是偶数，且对于所有偶数下标位置，该位置的元素不能等于下一个位置的元素。

贪心思路：

  1. 我们可以贪心地构造美丽数组，从左到右遍历原数组
  2. 对于每一对相邻元素，如果它们相等，我们必须删除其中一个
  3. 关键观察：当遇到相邻相等元素时，删除后面那个元素更优，因为这样不会影响前面已经配对好的元素
  4. 最后如果剩余元素个数是奇数，还需要再删除一个元素使长度变为偶数

具体算法：

  • 用一个指针模拟构造美丽数组的过程
  • 遍历原数组，对于每个元素，判断是否能与前一个未配对的元素组成有效对
  • 如果当前元素与前一个未配对元素相同，则删除当前元素（删除计数+1）
  • 否则，将当前元素加入结果中
  • 最终如果结果长度为奇数，需要额外删除一个元素

这种贪心策略是最优的，因为我们总是在必须删除时才删除，且选择删除不会影响已有配对的元素。

代码实现

class Solution {
public:
    int minDeletion(vector<int>& nums) {
        int deletions = 0;
        int validCount = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            // 如果当前位置是偶数位置且与下一个元素相等，删除下一个元素
            if (validCount % 2 == 0 && i + 1 < nums.size() && nums[i] == nums[i + 1]) {
                deletions++;
            } else {
                validCount++;
            }
        }
        
        // 如果最终长度是奇数，需要再删除一个
        if (validCount % 2 == 1) {
            deletions++;
        }
        
        return deletions;
    }
};

class Solution:
    def minDeletion(self, nums: List[int]) -> int:
        deletions = 0
        valid_count = 0
        
        i = 0
        while i < len(nums):
            # 如果当前是偶数位置且与下一个元素相等
            if valid_count % 2 == 0 and i + 1 < len(nums) and nums[i] == nums[i + 1]:
                deletions += 1
                i += 1  # 跳过下一个元素
            else:
                valid_count += 1
                i += 1
        
        # 如果最终长度是奇数，需要再删除一个
        if valid_count % 2 == 1:
            deletions += 1
            
        return deletions

public class Solution {
    public int MinDeletion(int[] nums) {
        int deletions = 0;
        int validCount = 0;
        
        for (int i = 0; i < nums.Length; i++) {
            // 如果当前位置是偶数位置且与下一个元素相等，删除下一个元素
            if (validCount % 2 == 0 && i + 1 < nums.Length && nums[i] == nums[i + 1]) {
                deletions++;
            } else {
                validCount++;
            }
        }
        
        // 如果最终长度是奇数，需要再删除一个
        if (validCount % 2 == 1) {
            deletions++;
        }
        
        return deletions;
    }
}

var minDeletion = function(nums) {
    let deletions = 0;
    let i = 0;
    
    while (i < nums.length - 1) {
        if (nums[i] === nums[i + 1]) {
            deletions++;
            i++;
        } else {
            i += 2;
        }
    }
    
    let remainingLength = nums.length - deletions;
    if (remainingLength % 2 === 1) {
        deletions++;
    }
    
    return deletions;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(1)

相关题目