1089. Duplicate Zeros

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.

 

Example 1:

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]
Example 2:

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

Note:

1 <= arr.length <= 10000
0 <= arr[i] <= 9

这题让我们把一个定长数组的0元素给复制一份，把后面的元素向下顺移。

假设我们从前往后开始挪动，时间复杂度会非常高，当然估计算法也能通过，就是运行时间难看了点。

所以这里我们可以从后开始遍历。

先遍历数组，计算出0的个数，这样我们在遍历的时候，就能直接计算出该元素应当处于的位置了。

每个元素，假设非0,则应当处于当前的位置加上之前0元素个数的偏移，假设可以放入数组，那么我们就放入对应的位置里。

假设为0,我们需要减去0元素的个数，并且计算当前0该处的位置，并且在之后再放一个0元素。

这样这题能够以O(N)来解决了。

class DuplicateZeros : public Solution {
public:
    void Exec() {
        vector<int> input1{1,2,3};
        duplicateZeros(input1);
    }
    void duplicateZeros(vector<int>& arr) {
        int zero_count = 0;
        for (auto &v : arr) {
            if (v == 0)
                zero_count++;
        }

        for (int i = arr.size() - 1; i >= 0; i--) {
            if (arr[i] == 0) {
                --zero_count;
                if (i + zero_count + 1 < arr.size()) {
                    arr[i + zero_count + 1] = 0;
                }
            }
            if (i + zero_count < arr.size()) {
                arr[i + zero_count] = arr[i];
            }
        }
    }
};