经典算法联系专区：复写零（二）

接上文我们来看解决方案思路和算法首先如果没有原地修改的限制那么我们可以另开辟一个栈来进行模拟放置而实际上我们可以不需要开辟栈空间来模拟放置元素我们只需要用两个指针来进行标记栈顶位置和现在需要放置的元素位置即可。我们用 top 来标记栈顶位置用 i 来标记现在需要放置的元素位置那么我们找到原数组中对应放置在最后位置的元素位置然后在数组最后从该位置元素往前来进行模拟放置即可。代码Python3class Solution: def duplicateZeros(self, arr: List[int]) - None: n len(arr) top 0 i -1 while top n: i 1 top 1 if arr[i] else 2 j n - 1 if top n 1: arr[j] 0 j - 1 i - 1 while j 0: arr[j] arr[i] j - 1 if arr[i] 0: arr[j] arr[i] j - 1 i - 1Cclass Solution { public: void duplicateZeros(vectorint arr) { int n arr.size(); int top 0; int i -1; while (top n) { i; if (arr[i] ! 0) { top; } else { top 2; } } int j n - 1; if (top n 1) { arr[j] 0; j--; i--; } while (j 0) { arr[j] arr[i]; j--; if (!arr[i]) { arr[j] arr[i]; j--; } i--; } } };Javaclass Solution { public void duplicateZeros(int[] arr) { int n arr.length; int top 0; int i -1; while (top n) { i; if (arr[i] ! 0) { top; } else { top 2; } } int j n - 1; if (top n 1) { arr[j] 0; j--; i--; } while (j 0) { arr[j] arr[i]; j--; if (arr[i] 0) { arr[j] arr[i]; j--; } i--; } } }复杂度分析时间复杂度O(n) 其中 n 为数组 arr 的长度需要遍历两遍数组。空间复杂度O(1) 仅使用常量空间。