力扣-美化数组的最少删除数

2023-11-21数据结构与算法2 分钟115 次阅读
AI 摘要salmon-ai

本文详细解析了力扣 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 个元素。

2216. 美化数组的最少删除数 原题链接

贪心解法

java 复制代码
public class Test {
    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 3, 5};
//        int[] nums = {1, 1, 2, 2, 3, 3, 3};
        System.out.println(minDeletion(nums));
    }

    public static int minDeletion(int[] nums) {
        int len = nums.length;
        int last = -1;
        int ans = 0;
        for (int i = 0; i < len; i++) {
            // 当前是新的连续相同元素的起始位置,将 last 设置为当前元素的值
            if (last == -1) {
                last = nums[i];
            }
            // 只关注当前需要保留多少个有效数字,
            // 比如当前待处理的数组是:{1, 1, 1, 2, 3, 5}
            // 相同元素的序列是从下标0位置的1开始,[1,1,1,2],2结束
            // 故我们只保留一开始的1和2,累计下有效的数字
            // 而这样的有效数字就是保留连续相同数字中的一个元素与之后中断连续的不同值的一个元素
            // 故进行 ans+=2
            // 故我们累计完有效数字后,然后重新让last记录连续相同数字的最开始的元素值
            if (nums[i] != last) {
                ans += 2;
                // 表示当前相同元素序列的结束,为下一个相同元素序列做准备
                last = -1;
            }
        }
        return len - ans;
    }
}
image.png

官方解法

java 复制代码
public class Test {
    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 1, 2, 2, 3, 4, 4, 5};
//        int[] nums = {1, 1, 2, 2, 3, 3};
        System.out.println(minDeletion1(nums));
    }

    public static int minDeletion(int[] nums) {
        int len = nums.length;
        // 删除元素的个数
        int ans = 0;
        // 当前下标是否是偶数,是偶数的话需要删除
        // 或者当前元素的值与下一个元素的值是否相等,相等则删除
        boolean check = true;
        for (int i = 0; i + 1 < len; ++i) {
            // 如果当前元素与下一个元素的值相等,且当前下标i是偶数
            if (nums[i] == nums[i + 1] && check) {
                ++ans;
            } else {
                // 因为删除了一个元素,则相应的原本下标要变成奇数或偶数
                // 这里用于表示当前下标是否是偶数状态的来回变换
                check = !check;
            }
        }
        // 如果数组长度减去被删除的元素的个数后是奇数,需再删除一个元素
        // 保持 nums.length 为偶数
        if ((len - ans) % 2 != 0) {
            ++ans;
        }
        return ans;
    }
}
image.png
觉得有用就点个赞,不用登录也能读

评论

0 条
登录 之后才能评论
—
还没有评论,来说第一句