Easy

题目描述

给你一个大小为 n 的 0 索引数组 nums，数组由非负整数组成。

你需要对这个数组执行 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

解题思路

这道题需要分两个阶段来解决：

解题思路

第一阶段：执行合并操作 我们需要从左到右遍历数组，对于每个位置 i（0 ≤ i < n-1），检查 nums[i] 是否等于 nums[i+1]：

  • 如果相等，将 nums[i] 乘以 2，将 nums[i+1] 置为 0
  • 如果不相等，跳过操作

这一步的关键是要按顺序执行，因为前面的操作可能会影响后面的判断。

第二阶段：移动零到末尾 执行完所有合并操作后，需要将数组中的所有 0 移动到末尾，保持非零元素的相对顺序不变。

有两种常见的实现方法：

  1. 双指针方法（推荐）：使用一个指针记录下一个非零元素应该放置的位置，遍历数组将非零元素前移，最后将剩余位置填充为 0。
  2. 新数组方法：创建新数组，先放入所有非零元素，再填充 0。

双指针方法更优，空间复杂度为 O(1)，而且逻辑清晰简洁。

代码实现

class Solution {
public:
    vector<int> applyOperations(vector<int>& nums) {
        int n = nums.size();
        
        // 第一阶段：执行合并操作
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                nums[i] *= 2;
                nums[i + 1] = 0;
            }
        }
        
        // 第二阶段：移动零到末尾
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != 0) {
                nums[left++] = nums[right];
            }
        }
        
        // 填充剩余位置为0
        while (left < n) {
            nums[left++] = 0;
        }
        
        return nums;
    }
};

class Solution:
    def applyOperations(self, nums: List[int]) -> List[int]:
        n = len(nums)
        
        # 第一阶段：执行合并操作
        for i in range(n - 1):
            if nums[i] == nums[i + 1]:
                nums[i] *= 2
                nums[i + 1] = 0
        
        # 第二阶段：移动零到末尾
        left = 0
        for right in range(n):
            if nums[right] != 0:
                nums[left] = nums[right]
                left += 1
        
        # 填充剩余位置为0
        while left < n:
            nums[left] = 0
            left += 1
        
        return nums

public class Solution {
    public int[] ApplyOperations(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;
            }
        }
        
        // 第二阶段：移动零到末尾
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != 0) {
                nums[left++] = nums[right];
            }
        }
        
        // 填充剩余位置为0
        while (left < n) {
            nums[left++] = 0;
        }
        
        return nums;
    }
}

var applyOperations = function(nums) {
    const n = nums.length;
    
    // 第一阶段：执行合并操作
    for (let i = 0; i < n - 1; i++) {
        if (nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，需要遍历数组两次，每次都是线性时间
空间复杂度O(1)，只使用了常数个额外变量，原地修改数组

相关题目