05 August 2008
给一个固定长度的Array，把里面的0都duplicate以下，超过size的元素往右遍shift不见
two passes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
O(n) runtime
O(1) space
*/
public void duplicateZeros(int[] A) {
int n = A.length, count = 0;
for (int num : A) if (num == 0) count++;
int i = n - 1;
int write = n + count - 1;
while (i >= 0 && write >= 0) {
if (A[i] != 0) { // Non-zero, just write it in
if (write < n) A[write] = A[i];
} else { // Zero found, write it in twice if we can
if (write < n) A[write] = A[i];
write--;
if (write < n) A[write] = A[i];
}
i--;
write--;
}
}