1089. 复写零

🟢   🔖  数组 双指针  🔗 力扣 LeetCode

题目

Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written. Do the above modifications to the input array in place and do not return anything.

Example 1:

Input: arr = [1,0,2,3,0,4,5,0]

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

Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

Example 2:

Input: arr = [1,2,3]

Output: [1,2,3]

Explanation: After calling your function, the input array is modified to: [1,2,3]

Constraints:

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 9

题目大意

给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地进行上述修改，不要从函数返回任何东西。

示例 1：

输入： arr = [1,0,2,3,0,4,5,0]

输出：[1,0,0,2,3,0,0,4]

解释： 调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

示例 2：

输入： arr = [1,2,3]

输出：[1,2,3]

解释： 调用函数后，输入的数组将被修改为：[1,2,3]

提示：

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 9

解题思路

题目要求不能使用额外空间，仅通过调整现有数组的元素完成操作。

1. 标记最后能被复写的元素索引：

   • 遍历数组，计算哪些元素会被复写。
   • 使用 lastKeepIdx 标记最后一个能够保留的非零元素。
   • 使用 lastZeroIdx 标记最后一个需要复写的零。

2. 从后向前进行复写：

   • 从数组末尾开始填充元素，以避免复写时覆盖未处理的元素。
   • 遇到 0 时，复写两次（需要保证复写范围在 lastZeroIdx 以内）。

复杂度分析

• 时间复杂度：O(n)，第一次遍历标记有效范围，第二次遍历完成复写，均为线性复杂度。
• 空间复杂度：O(1)，不使用额外空间，原地修改。

代码

/**
 * @param {number[]} arr
 * @return {void} Do not return anything, modify arr in-place instead.
 */
var duplicateZeros = function (arr) {
	const n = arr.length;
	let lastKeepIdx = n - 1;
	let lastZeroIdx;
	for (let i = 0; i <= lastKeepIdx; i++) {
		if (arr[i] == 0 && i !== lastKeepIdx) {
			lastKeepIdx--; // 每发现一个可复写的零，调整最后保留索引
			lastZeroIdx = i; // 更新最后一个复写零的位置
		}
	}
	if (lastKeepIdx < n - 1) {
		for (let i = n - 1; lastKeepIdx >= 0; i--) {
			arr[i] = arr[lastKeepIdx]; // 将最后一个未复写元素复制到当前位置
			if (arr[lastKeepIdx] == 0 && lastKeepIdx <= lastZeroIdx) {
				arr[i - 1] = 0; // 复写零到前一个位置
				i--; // 跳过已复写的零
			}
			lastKeepIdx--; // 更新未复写的最后元素索引
		}
	}
};