1089. Duplicate Zeros

public class Solution {
    public void DuplicateZeros(int[] arr) {
        int possibleDups = 0;
        int length_ = arr.Length - 1;
        for (int left = 0; left <= length_ - possibleDups; left++) {
            if (arr[left] == 0) {
                if (left == length_ - possibleDups) {
                    arr[length_] = 0;
                    length_ -= 1;
                    break;
                }
                possibleDups++;
            }
        }
        int last = length_ - possibleDups;
        for (int i = last; i >= 0; i--) {
            if (arr[i] == 0) {
                arr[i + possibleDups] = 0;
                possibleDups--;
                arr[i + possibleDups] = 0;
            } else {
                arr[i + possibleDups] = arr[i];
            }
        }
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public void DuplicateZeros(vector<int>& arr) {
        int possibleDups = 0;
        int length_ = arr.size() - 1;
        for (int left = 0; left <= length_ - possibleDups; left++) {
            if (arr[left] == 0) {
                if (left == length_ - possibleDups) {
                    arr[length_] = 0;
                    length_ -= 1;
                    break;
                }
                possibleDups++;
            }
        }
        int last = length_ - possibleDups;
        for (int i = last; i >= 0; i--) {
            if (arr[i] == 0) {
                arr[i + possibleDups] = 0;
                possibleDups--;
                arr[i + possibleDups] = 0;
            } else {
                arr[i + possibleDups] = arr[i];
            }
        }
    }
}

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public void DuplicateZeros(int[] arr) {
        int possibleDups = 0;
        int length_ = arr.length - 1;
        for (int left = 0; left <= length_ - possibleDups; left++) {
            if (arr[left] == 0) {
                if (left == length_ - possibleDups) {
                    arr[length_] = 0;
                    length_ -= 1;
                    break;
                }
                possibleDups++;
            }
        }
        int last = length_ - possibleDups;
        for (int i = last; i >= 0; i--) {
            if (arr[i] == 0) {
                arr[i + possibleDups] = 0;
                possibleDups--;
                arr[i + possibleDups] = 0;
            } else {
                arr[i + possibleDups] = arr[i];
            }
        }
    }
}

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        possibleDups = 0
        length_ = len(arr) - 1

        for left in range(length_ + 1):
            if left > length_ - possibleDups:
                break
            if arr[left] == 0:
                if left == length_ - possibleDups:
                    arr[length_] = 0
                    length_ -= 1
                    break
                possibleDups += 1

        last = length_ - possibleDups

        for i in range(last, -1, -1):
            if arr[i] == 0:
                arr[i + possibleDups] = 0
                possibleDups -= 1
                arr[i + possibleDups] = 0
            else:
                arr[i + possibleDups] = arr[i]

func duplicateZeros(arr []int) {
    possibleDups := 0
    length_ := len(arr) - 1

    for left := 0; left <= length_ - possibleDups; left++ {
        if arr[left] == 0 {
            if left == length_ - possibleDups {
                arr[length_] = 0
                length_--
                break
            }
            possibleDups++
        }
    }

    last := length_ - possibleDups

    for i := last; i >= 0; i-- {
        if arr[i] == 0 {
            arr[i + possibleDups] = 0
            possibleDups--
            arr[i + possibleDups] = 0
        } else {
            arr[i + possibleDups] = arr[i]
        }
    }
}

Algorithm

find количество нулей, которые будут продублированы, назовем это possible_dups. Необходимо убедиться, что мы не считаем нули, которые будут отброшены, так как отброшенные нули не будут частью итогового arrayа. Количество possible_dups даст нам количество elementов, которые будут отброшены из исходного arrayа. В любой момент времени length_ - possible_dups — это количество elementов, которые будут включены в итоговый array.

Обработайте крайний случай для нуля, находящегося на границе оставшихся elementов. Будьте особенно внимательны при дублировании нулей в оставшемся arrayе. Следует учитывать, лежит ли ноль на границе. Этот ноль может быть учтен с возможными дубликатами или может быть просто включен в оставшиеся elementы, когда не осталось места для его дубликата. Если он является частью possible_dups, мы хотим его дублировать, в противном случае — нет.

Итерируйте array с конца и копируйте ненулевой element один раз, а нулевой element дважды. Когда мы говорим об отбрасывании лишних elementов, это означает, что мы начинаем с левой стороны лишних elementов и начинаем перезаписывать их новыми значениями, в конечном итоге сдвигая оставшиеся elementы вправо и создавая пространство для всех дублированных elementов в arrayе.

😎