Duplicate Zeros

往后加一个0，然后移动其他数

class Solution {
    public void duplicateZeros(int[] arr) {
        for(int i = 0; i < arr.length; i++) {
            if(arr[i] == 0 && i+1 < arr.length) { //find the position of zero
                int t = arr[i+1]; // cache the value of next non-zero
                arr[i+1] = 0; // set next to zero
                for(int p = i+2; p < arr.length; p++){ // roll all value to next position
                    int pp = arr[p];
                    arr[p] = t;
                    t = pp;
                }
                i++;//update i to next position.
            }
        }
    }
}

看到讨论里有个o(1) time, o(n) space的, 利用queue作为结果的预存储:

class Solution {
    public void duplicateZeros(int[] arr) {
        Queue<Integer> q = new LinkedList<Integer>();
        for(int i = 0 ; i < arr.length; i++) {
            q.add(arr[i]);
            if(arr[i] == 0) {
                q.add(0);
            }
            arr[i] = q.remove();
        }
    }
}