1089. Duplicate Zeros

題目敘述

Given a fixed-length integer array arr, 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 and do not return anything.

Example 1:

Input: arr = [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

Example 2:

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

Constraints:

• 1 <= arr.length <= 10**4
• 0 <= arr[i] <= 9

Hint 1

This is a great introductory problem for understanding and working with the concept of in-place operations. The problem statement clearly states that we are to modify the array in-place. That does not mean we cannot use another array. We just don't have to return anything.

Hint 2

A better way to solve this would be without using additional space. The only reason the problem statement allows you to make modifications in place is that it hints at avoiding any additional memory.

Hint 3

The main problem with not using additional memory is that we might override elements due to the zero duplication requirement of the problem statement. How do we get around that?

Hint 4

If we had enough space available, we would be able to accommodate all the elements properly. The new length would be the original length of the array plus the number of zeros. Can we use this information somehow to solve the problem?

題目翻譯

給定一個整數陣列 nums，然後當發現 0 值時就複製兩個值，將後面的元素向後挪移。如果超出原本陣列長度的元素就直接拋棄。

解法解析

這題的解法使用的兩個迴圈處理，第一個迴圈用來找出 0 的數量。

    // 遍歷全部
    for (let i = 0; i <= length_; i++) {
        // 當現在的索引 i + possibleDups > 總長 length_ 的會就中斷
        // 因為後續的元素會被拋棄，所以不需要考慮
        if (i > length_ - possibleDups) {
            break;
        }


        if (arr[i] === 0) {
            // 當索引是最後一位時，做處理
            if (i === length_ - possibleDups) {
                arr[length_] = 0;
                length_--;
                break;
            }
            // 紀錄個數
            possibleDups++;
        }
    }

所以經過上面的處理後原本陣列 arr = [1, 0, 2] 的長度，其實只需要處理 2 個長度而已。容後第二個迴圈從後面往前走，每次遞減 possibleDups。

    const last = length_ - possibleDups;
    for (let i = last; i >= 0; i--) {
        arr[i + possibleDups] = arr[i];
        if (arr[i] === 0) {
            possibleDups--;
            arr[i + possibleDups] = arr[i];
        }
    }

解法範例

Go

func duplicateZeros(arr []int) {
    var possibleDups, length_ int = 0, len(arr) - 1
    for i := 0; i <= length_; i++ {
        if i > length_-possibleDups {
            break
        }
        if arr[i] == 0 {
            if i == length_-possibleDups {
                arr[length_] = 0
                length_--
                break
            }
            possibleDups++
        }
    }

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

JavaScript

/**
 * @param {number[]} arr
 * @return {void} Do not return anything, modify arr in-place instead.
 */
var duplicateZeros = function (arr) {
    let possibleDups = 0,
        length_ = arr.length - 1;
    for (let i = 0; i <= length_; i++) {
        if (i > length_ - possibleDups) {
            break;
        }

        if (arr[i] === 0) {
            if (i === length_ - possibleDups) {
                arr[length_] = 0;
                length_--;
                break;
            }
            possibleDups++;
        }
    }

    const last = length_ - possibleDups;
    for (let i = last; i >= 0; i--) {
        arr[i + possibleDups] = arr[i];
        if (arr[i] === 0) {
            possibleDups--;
            arr[i + possibleDups] = arr[i];
        }
    }
};

Kotlin

class Solution {
    fun duplicateZeros(arr: IntArray): Unit {
        var possibleDups: Int = 0
        var length_: Int = arr.size - 1
        for (i in 0..length_) {
            if (i > length_ - possibleDups) {
                break
            }

            if (arr[i] == 0) {
                if (i == length_ - possibleDups) {
                    arr[length_] = 0
                    length_--
                    break
                }
                possibleDups++
            }
        }

        val last = length_ - possibleDups
        for (i in last downTo 0) {
            arr[i + possibleDups] = arr[i]
            if (arr[i] == 0) {
                possibleDups--
                arr[i + possibleDups] = arr[i]
            }
        }
    }
}

PHP

class Solution
{

    /**
     * @param Integer[] $arr
     * @return NULL
     */
    function duplicateZeros(&$arr)
    {
        $possibleDups = 0;
        $length_ = count($arr) - 1;
        for ($i = 0; $i <= $length_; $i++) {
            if ($i > $length_ - $possibleDups) {
                break;
            }
            if ($arr[$i] == 0) {
                if ($i == $length_ - $possibleDups) {
                    $arr[$length_] = 0;
                    $length_--;
                    break;
                }
                $possibleDups++;
            }
        }

        $last = $length_ - $possibleDups;
        for ($i = $last; $i >= 0; $i--) {
            $arr[$i + $possibleDups] = $arr[$i];
            if ($arr[$i] == 0) {
                $possibleDups--;
                $arr[$i + $possibleDups] = $arr[$i];
            }
        }
    }
}

Python

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        possible_dups = 0
        length_ = len(arr) - 1

        # Find the number of zeros to be duplicated
        for left in range(length_ + 1):

            # Stop when left points beyond the last element in the original list
            # which would be part of the modified list
            if left > length_ - possible_dups:
                break

            # Count the zeros
            if arr[left] == 0:
                # Edge case: This zero can't be duplicated. We have no more space,
                # as left is pointing to the last element which could be included
                if left == length_ - possible_dups:
                    arr[
                        length_
                    ] = 0  # For this zero we just copy it without duplication.
                    length_ -= 1
                    break
                possible_dups += 1

        # Start backwards from the last element which would be part of new list.
        last = length_ - possible_dups

        # Copy zero twice, and non zero once.
        for i in range(last, -1, -1):
            arr[i + possible_dups] = arr[i]
            if arr[i] == 0:
                possible_dups -= 1
                arr[i + possible_dups] = arr[i]

Rust

Swift

class Solution {
    func duplicateZeros(_ arr: inout [Int]) {
        var possibleDups: Int = 0
        var length_: Int = arr.count - 1
        for i in 0...length_ {
            if i > length_ - possibleDups {
                break
            }

            if arr[i] == 0 {
                if i == length_ - possibleDups {
                    arr[length_] = 0
                    length_ -= 1
                    break
                }

                possibleDups += 1
            }
        }

        var i: Int = length_ - possibleDups
        while i >= 0 {
            arr[i + possibleDups] = arr[i]
            if arr[i] == 0 {
                possibleDups -= 1
                arr[i + possibleDups] = arr[i]
            }
            i -= 1
        }
    }
}