2460. 对数组执行操作

🟢   🔖  数组 双指针 模拟  🔗 力扣 LeetCode

题目

You are given a 0-indexed array nums of size n consisting of non- negative integers.

You need to apply n - 1 operations to this array where, in the ith operation (0-indexed), you will apply the following on the ith element of nums:

• If nums[i] == nums[i + 1], then multiply nums[i] by 2 and set nums[i + 1] to 0. Otherwise, you skip this operation.

After performing all the operations, shift all the 0's to the end of the array.

• For example, the array [1,0,2,0,0,1] after shifting all its 0's to the end, is [1,2,1,0,0,0].

Return the resulting array.

Note that the operations are applied sequentially , not all at once.

Example 1:

Input: nums = [1,2,2,1,1,0]

Output: [1,4,2,0,0,0]

Explanation: We do the following operations:

• i = 0: nums[0] and nums[1] are not equal, so we skip this operation.
• i = 1: nums[1] and nums[2] are equal, we multiply nums[1] by 2 and change nums[2] to 0. The array becomes [1,4 ,0 ,1,1,0].
• i = 2: nums[2] and nums[3] are not equal, so we skip this operation.
• i = 3: nums[3] and nums[4] are equal, we multiply nums[3] by 2 and change nums[4] to 0. The array becomes [1,4,0,2 ,0 ,0].
• i = 4: nums[4] and nums[5] are equal, we multiply nums[4] by 2 and change nums[5] to 0. The array becomes [1,4,0,2,0 ,0].

After that, we shift the 0's to the end, which gives the array [1,4,2,0,0,0].

Example 2:

Input: nums = [0,1]

Output: [1,0]

Explanation: No operation can be applied, we just shift the 0 to the end.

Constraints:

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

题目大意

给你一个下标从 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

解题思路

1. 合并相邻相等元素

   • 遍历数组 nums，检查相邻元素 nums[i] 和 nums[i+1] 是否相等且非零。
   • 如果相等，执行 nums[i] *= 2，并将 nums[i + 1] = 0。

2. 移动非零元素

   • 使用 双指针 方法：
     • 指针 slow 指向下一个要放置非零元素的位置。
     • 指针 fast 遍历数组：
       • 将所有非零元素按顺序填入 nums[slow]；
       • 若 fast !== slow，将 nums[fast] 置为 0；
       • 更新 slow；
     • 遍历结束后，所有非零元素已经左移。

复杂度分析

• 时间复杂度：O(n)，遍历数组两次（一次合并，一次移动）。
• 空间复杂度：O(1)，原地修改 nums，不额外使用数组。

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var applyOperations = function (nums) {
	const n = nums.length;

	// 合并相邻相同的非零元素
	for (let i = 0; i < n - 1; i++) {
		if (nums[i] === nums[i + 1] && nums[i] !== 0) {
			nums[i] *= 2;
			nums[i + 1] = 0;
		}
	}

	// 双指针移动非零元素
	let slow = 0;
	for (let fast = 0; fast < n; fast++) {
		const num = nums[fast];
		if (nums[fast] !== 0) {
			nums[slow] = num;
			if (slow !== fast) {
				nums[fast] = 0;
			}
			slow++;
		}
	}

	return nums;
};

相关题目

题号	标题	题解	标签	难度	力扣
26	删除有序数组中的重复项	[✓]	数组 双指针	🟢	🀄️ 🔗
283	移动零	[✓]	数组 双指针	🟢	🀄️ 🔗