『LeetCode』2216 美化数组的最少删除数

题目

2216. 美化数组的最少删除数

给你一个下标从 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^{5}\)
\(0 <= nums[i] <= 10^{5}\)

题解

【美化数组的最少删除数】简单贪心

贪心

可以换个角度思考，考虑如何构建一个最长的美化数组。

首先，对于偶数位置的数字是可以随意放置，没有约束的，但对于奇数位置上的数字则要求不能与对应偶数位置的相同，不难想到如下贪心算法：

从左向右遍历数组，对于新构建数组的偶数位置，直接置入
对于奇数位置，如不相同则直接置入，相同则舍弃
构建的最长数组与原数组长度差即答案

当然，最后还有注意一点的是题目要求数组长度为偶数，所以若构建的数组是奇数长度，要舍去最后一个数。

# Code language: Python
class Solution:
    def minDeletion(self, nums: List[int]) -> int:
        ans = list()
        for a in nums:
            if len(ans) % 2 == 0 or ans[-1] != a:
                ans.append(a)
        return len(nums) - len(ans) // 2 * 2

// Code language: Java
class Solution {
    public int minDeletion(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        for (int a: nums) {
            if (ans.size() % 2 == 0 || ans.get(ans.size() - 1) != a) {
                ans.add(a);
            }
        }
        return nums.length - ans.size() / 2 * 2;
    }
}

// Code language: C++
class Solution {
public:
    int minDeletion(vector<int>& nums) {
        vector<int> ans;
        for (int a: nums) {
            if (ans.size() % 2 == 0 || ans.back() != a) {
                ans.emplace_back(a);
            }
        }
        return nums.size() - ans.size() / 2 * 2;
    }
};

/* Code language: Go */
func minDeletion(nums []int) int {
    var ans []int
    for _, a := range nums {
        if len(ans)%2 == 0 || ans[len(ans)-1] != a {
            ans = append(ans, a)
        }
    }
    return len(nums) - len(ans) / 2 * 2
}

时间复杂度: \(O(n)\)
空间复杂度: \(O(n)\)

空间优化

实际上我们不需要真的将美化数组构建出来，只需记录下构建数组的长度即可，对于构建数组，我们只需要记录数组中最后一个数即可用于判断后续数字是否能加入到构建的数组中。

再进一步，我们甚至无需记录最后一个数，考察构建数组，偶数位置与下一个相邻的奇数位置不同，所以对于数组中连续的一段值相同的数字，只能取一个，这启示着我们只需要判断构造数组在偶数位置上的数值必须是原数组中与下一个位置不同的数，即奇数位置的数要满足 nums[i] != nums[i + 1]

例如对于 [1,1,1,1,1,2,2,3], 构建的美化数组为 [1,2,2,3], 新构建的数组在下标为 0 的位置要满足 nums[i] != nums[i + 1] 即下标为 4 的 1 (连续 1 中最后一个)，但对于奇数位置例如下标为 1 的数值没有要求。

# Code language: Python
class Solution:
    def minDeletion(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        for i in range(n):
            if ans % 2 == 1 or i + 1 >= n or nums[i] != nums[i + 1]:
                ans += 1
        return n - ans // 2 * 2

// Code language: Java
class Solution {
    public int minDeletion(int[] nums) {
        int ans = 0;
        for (int i = 0, n = nums.length; i < n; i++) {
            if (ans % 2 == 1 || i + 1 >= n || nums[i] != nums[i + 1]) {
                ans++;
            }
        }
        return nums.length - ans / 2 * 2;
    }
}

// Code language: C++
class Solution {
public:
    int minDeletion(vector<int>& nums) {
        int ans = 0;
        for (int i = 0, n = nums.size(); i < n; i++) {
            if (ans % 2 == 1 || i + 1 >= n || nums[i] != nums[i + 1]) {
                ans++;
            }
        }
        return nums.size() - ans / 2 * 2;
    }
};

/* Code language: Go */
func minDeletion(nums []int) int {
    n, ans := len(nums), 0
    for i := 0; i < n; i++ {
        if ans % 2 == 1 || i + 1 >= n || nums[i] != nums[i + 1] {
            ans++
        }
    }
    return n - ans / 2 * 2
}

时间复杂度: \(O(n)\)
空间复杂度: \(O(1)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』2216 美化数组的最少删除数

题目

标签

题解

贪心

空间优化