leetcode
leetcode 2151 ~ 2200
对数组执行操作

对数组执行操作

难度:

标签:

题目描述

代码结果

运行时间: 22 ms, 内存: 16.2 MB


/*
 * 思路:
 * 1. 使用流操作对数组进行处理。
 * 2. 首先对数组进行遍历,如果相邻两个元素相等,按规则修改数组。
 * 3. 最后通过流将非零元素提取出来,并在末尾补充0。
 */

import java.util.Arrays;
import java.util.stream.Collectors;

public int[] processArrayStream(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            nums[i] *= 2;
            nums[i + 1] = 0;
        }
    }
    return Arrays.stream(nums)
                 .filter(num -> num != 0)
                 .boxed()
                 .collect(Collectors.toList())
                 .stream()
                 .flatMap(num -> Arrays.stream(new int[]{num, 0}).limit(num == 0 ? 0 : 1))
                 .mapToInt(i -> i)
                 .toArray();
}

解释

方法:

首先遍历数组 `nums`,对于每个元素 `nums[i]`,如果它和下一个元素 `nums[i+1]` 相等,则将 `nums[i]` 更新为其两倍,并将 `nums[i+1]` 设置为0。接着,再次遍历数组,将非零元素放入列表 `ans1`,将零元素放入列表 `ans2`。这样做的目的是为了将所有非零元素保持原有顺序,而将零元素移动到数组的末尾。最后,返回 `ans1` 和 `ans2` 的合并结果,即为最终数组。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在算法中,为什么选择在操作完成后再分别处理零和非零元素,而不是在进行倍增操作时直接调整元素的位置?
选择在操作完成后再分别处理零和非零元素主要是为了简化代码逻辑并提高效率。在进行倍增操作时,如果直接调整元素位置,会导致数组中元素频繁移动,增加算法的复杂度。同时,通过先对数组进行处理,再统一调整位置,可以保持代码的清晰性和可维护性。这种方法也利于后续可能的优化或变更,因为它将变更局限于非零和零元素的分离过程,而不是分散在整个算法中。
🦆
如果数组中存在多个连续的相同值,例如 [2,2,2,2],算法如何确保正确地处理这种情况?会不会存在遗漏或重复倍增的问题?
当前算法实现在处理连续相同值时可能会存在问题。以 [2,2,2,2] 为例,按照现有的算法步骤,第一轮循环将第一个 '2' 变为 '4' 并将第二个 '2' 置为 '0',结果是 [4,0,2,2]。但接下来的元素处理时,第三个 '2' 并不会与前一个 '0' 进行倍增操作,从而导致第三个和第四个 '2' 只会处理成 [4,0,4,0]。这说明算法在处理连续相同值时会遗漏部分倍增机会,不会重复倍增,但会错过一些应执行的倍增。
🦆
为什么在处理完 `nums[i]` 和 `nums[i+1]` 后,没有跳过已经设为0的 `nums[i+1]` 在下一次循环时再次检查?
算法中没有跳过已设为0的 `nums[i+1]` 是因为简化了循环控制逻辑。跳过这个检查可能需要引入额外的控制变量或修改循环条件,这可能导致代码更复杂。虽然这样做在某些情况下会稍微增加计算量,但避免了复杂的跳跃逻辑,使代码更易理解和维护。此外,这种方式确保了算法的稳定性,因为每个元素都被检查到,不会因为跳过检查而漏掉某些可能的操作。
🦆
在返回结果时,合并 `ans1` 和 `ans2` 的操作是否会影响数组中元素的原始相对顺序,尤其是在存在多个0的情况下?
在返回结果时,合并 `ans1` 和 `ans2` 的操作不会影响非零元素之间的原始相对顺序,因为所有非零元素都按照它们在原数组中的顺序被添加到 `ans1` 中。然而,所有的零元素被集中放置在数组的末尾,这种处理方式虽然改变了零元素原始的相对位置,但保持了非零元素的相对顺序。因此,这种方法适合于需要将零元素移至数组末尾的场景,而对非零元素的顺序有严格保持的需求。

相关问题