Given a fixed length array arr of integers, 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, do not return anything from your function.
Input: [1,0,2,3,0,4,5,0] Output: null Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]Note:
1 <= arr.length <= 10000 0 <= arr[i] <= 9
…
class Solution { public void duplicateZeros(int[] a) { int n = a.length; List<Integer> nums = new ArrayList<>(2); for (int i : a) nums.add(i); for (int i = 0; i < n; ) { if (nums.get(i) == 0) { nums.add(i+1, 0); i+=2; } else { i++; } } for (int i = 0; i < n; i++) a[i] = nums.get(i); } }优化思路
ArrayList 的插入是 O(n) 的,但我们并不需要真的将原数组拷贝经 List 中,然后在进行插入,取而代之的是:
遇到 0 就将 0 放到一个队列 q 中,当队列 q 不空时,证明有 0 需要被复写,但此时的 0 后面的元素我们不能让它丢失,所以我们也将其保存到队列 q 中
class Solution { public void duplicateZeros(int[] a) { Queue<Integer> q = new LinkedList<>(); for (int i = 0; i < a.length; i++) { if (a[i] == 0) q.add(0); if (!q.isEmpty()) { q.add(a[i]); a[i] = q.poll(); } } } }思路
如果某一个非零元素的前面有 k 个 0,那么这个非零元素的后面 k 个位置都会被替换,基于这一点,我们可以先统计 0 的个数,然后反向遍历:
遇到非 0 元素 a[i] 时,说明 a[i] 是要被移动 k 个位置的遇到 0 元素 a[i] 时,也说明 a[i] 是要被移动 k 个位置的,但移动的时候我们还要将 0 进行复制,所以 0 后面 k、k+1 这两个位置是要被改为 0 的 class Solution { public void duplicateZeros(int[] a) { int k = 0, n = a.length; for (int i : a) if (i == 0) k++; for (int i = n-1; i >= 0; i--) { if (a[i] == 0) { k--; if (i + k < n) a[i+k] = 0; if (i + k + 1 < n) a[i+k+1] = 0; } else if (i + k < n) { a[i+k] = a[i]; } } } }