美化数组的最少删除数

难度:

标签:

题目描述

代码结果

运行时间: 70 ms, 内存: 27.3 MB

/*
 * 思路：
 * 1. 使用Java Stream API来遍历数组并检查每个偶数索引的元素和下一个元素是否相等。
 * 2. 使用IntStream来生成偶数索引，然后使用filter和count方法来统计需要删除的元素数量。
 */
import java.util.stream.IntStream;

public class Solution {
    public int minDeletions(int[] nums) {
        return (int) IntStream.range(0, nums.length - 1)
                              .filter(i -> i % 2 == 0 && nums[i] == nums[i + 1])
                              .count();
    }
}

解释

方法:

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

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

在这个算法中，为什么初始化`left`为-1而不是使用一个布尔变量来判断是否有悬挂的元素？

▷

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

🦆

算法如何处理连续相同元素超过两个的情况，比如输入是[1,1,1,2]？

▷

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

🦆

算法最后通过`int(left >= 0)`来决定是否需要额外删除一个元素，这种方法是否能准确处理所有情况，例如当数组长度为奇数但最后一个元素已经被计入删除时的情况？

▷

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

🦆

算法中提到如果`x != left`则构成一对有效的美丽数组元素，但算法实际上并没有构建或返回这样的一对数组，而是重置了`left`，这种方法是否确实符合题目要求的最少删除次数来构造美丽数组？

▷

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

美化数组的最少删除数

题目描述

代码结果

解释

代码细节讲解

相关问题