对数组执行操作

标签: 数组模拟

难度: Easy

给你一个下标从 0 开始的数组 nums ，数组大小为 n ，且由非负整数组成。

你需要对数组执行 n - 1 步操作，其中第 i 步操作（从 0 开始计数）要求对 nums 中第 i 个元素执行下述指令：

如果 nums[i] == nums[i + 1] ，则 nums[i] 的值变成原来的 2 倍，nums[i + 1] 的值变成 0 。否则，跳过这步操作。

在执行完全部操作后，将所有 0 移动到数组的末尾。

例如，数组 [1,0,2,0,0,1] 将所有 0 移动到末尾后变为 [1,2,1,0,0,0] 。

返回结果数组。

注意操作应当 依次有序 执行，而不是一次性全部执行。

示例 1：

输入：nums = [1,2,2,1,1,0]
输出：[1,4,2,0,0,0]
解释：执行以下操作：
- i = 0: nums[0] 和 nums[1] 不相等，跳过这步操作。
- i = 1: nums[1] 和 nums[2] 相等，nums[1] 的值变成原来的 2 倍，nums[2] 的值变成 0 。数组变成 [1,4,0,1,1,0] 。
- i = 2: nums[2] 和 nums[3] 不相等，所以跳过这步操作。
- i = 3: nums[3] 和 nums[4] 相等，nums[3] 的值变成原来的 2 倍，nums[4] 的值变成 0 。数组变成 [1,4,0,2,0,0] 。
- i = 4: nums[4] 和 nums[5] 相等，nums[4] 的值变成原来的 2 倍，nums[5] 的值变成 0 。数组变成 [1,4,0,2,0,0] 。
执行完所有操作后，将 0 全部移动到数组末尾，得到结果数组 [1,4,2,0,0,0] 。

示例 2：

输入：nums = [0,1]
输出：[1,0]
解释：无法执行任何操作，只需要将 0 移动到末尾。

提示：

2 <= nums.length <= 2000
0 <= nums[i] <= 1000

Submission

运行时间: 22 ms

内存: 16.2 MB

class Solution:
    def applyOperations(self, nums: List[int]) -> List[int]:
        ans1,ans2 = [],[]
        for i in range(len(nums)-1):
            if nums[i] == nums[i+1]:
                nums[i] *= 2
                nums[i+1] = 0
            if nums[i] != 0:
                ans1.append(nums[i])
            else:
                ans2.append(nums[i])
        if nums[-1] != 0:
            ans1.append(nums[-1])
        else:
            ans2.append(nums[-1])
        return ans1 + ans2

Explain

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

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def applyOperations(self, nums: List[int]) -> List[int]:
        ans1, ans2 = [], []  # 分别用于存储非零元素和零元素
        # 遍历数组，进行倍增和置零操作
        for i in range(len(nums) - 1):
            if nums[i] == nums[i + 1]:
                nums[i] *= 2  # 将当前元素加倍
                nums[i + 1] = 0  # 将下一个元素置为0
            # 根据当前元素是否为零，将其加入到相应列表
            if nums[i] != 0:
                ans1.append(nums[i])
            else:
                ans2.append(nums[i])
        # 处理最后一个元素
        if nums[-1] != 0:
            ans1.append(nums[-1])
        else:
            ans2.append(nums[-1])
        # 将非零元素列表和零元素列表合并并返回
        return ans1 + ans2

Explore

选择在操作完成后再分别处理零和非零元素主要是为了简化代码逻辑并提高效率。在进行倍增操作时，如果直接调整元素位置，会导致数组中元素频繁移动，增加算法的复杂度。同时，通过先对数组进行处理，再统一调整位置，可以保持代码的清晰性和可维护性。这种方法也利于后续可能的优化或变更，因为它将变更局限于非零和零元素的分离过程，而不是分散在整个算法中。

当前算法实现在处理连续相同值时可能会存在问题。以 [2,2,2,2] 为例，按照现有的算法步骤，第一轮循环将第一个 '2' 变为 '4' 并将第二个 '2' 置为 '0'，结果是 [4,0,2,2]。但接下来的元素处理时，第三个 '2' 并不会与前一个 '0' 进行倍增操作，从而导致第三个和第四个 '2' 只会处理成 [4,0,4,0]。这说明算法在处理连续相同值时会遗漏部分倍增机会，不会重复倍增，但会错过一些应执行的倍增。

算法中没有跳过已设为0的 `nums[i+1]` 是因为简化了循环控制逻辑。跳过这个检查可能需要引入额外的控制变量或修改循环条件，这可能导致代码更复杂。虽然这样做在某些情况下会稍微增加计算量，但避免了复杂的跳跃逻辑，使代码更易理解和维护。此外，这种方式确保了算法的稳定性，因为每个元素都被检查到，不会因为跳过检查而漏掉某些可能的操作。

在返回结果时，合并 `ans1` 和 `ans2` 的操作不会影响非零元素之间的原始相对顺序，因为所有非零元素都按照它们在原数组中的顺序被添加到 `ans1` 中。然而，所有的零元素被集中放置在数组的末尾，这种处理方式虽然改变了零元素原始的相对位置，但保持了非零元素的相对顺序。因此，这种方法适合于需要将零元素移至数组末尾的场景，而对非零元素的顺序有严格保持的需求。