LeetCode Solution, Easy, 283. Move Zeroes

移動零值

283. Move Zeroes

題目敘述

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:

Input: nums = [0]
Output: [0]

Constraints:

  • 1 <= nums.length <= 10**4
  • -2**31 <= nums[i] <= 2**31 - 1

Follow up: Could you minimize the total number of operations done?

Hint 1

In-place means we should not be allocating any space for extra array. But we are allowed to modify the existing array. However, as a first step, try coming up with a solution that makes use of additional space. For this problem as well, first apply the idea discussed using an additional array and the in-place solution will pop up eventually.

Hint 2

A two-pointer approach could be helpful here. The idea would be to have one pointer for iterating the array and another pointer that just works on the non-zero elements of the array.

題目翻譯

有個整數陣列 nums,需要將其中為 0 的元素往後挪移。而其他非 0 的數值需要保持其排序。必須使用 In-place 的方式來解答,可以嘗試利用 two-pointer 來降低複雜度。

解法解析

官方提供了三種解法,當然解法不止這三種,不同語言也有不同的特性或語法糖可以使用。可以各自變化,這邊只是解釋三種解法的解題思路。

Space Sub-Optimal

分成幾個步驟:

  1. 先用一層迴圈找出 0 的數量 numZeroesO(n)
  2. 跑一層迴圈只出非 0 的元素,放到另一個陣列 arr。Worest case:O(n) 全部都非 0
  3. 跑一層迴圈將在第一步驟求出的 0 數量,放到 arr 中。Worest case:O(n) 全部都是 0
  4. arr 的值都轉換到 numsO(n)

時間複雜度:O(n)O(4n) => O(n)

空間複雜度:O(n)

Space Optimal, Operation Sub-Optimal

使用 two-pointer 的方式,一個去記上次 0 值的位置,一個是目前遍歷的索引位置。

  1. 第一個迴圈將所有的非 0 值往前放,用 lastNonZeroFoundAt 紀錄目前最後出現的 0 在哪個位置。
  2. lastNonZeroFoundAt 的位置到結尾都直接設定為 0

時間複雜度:O(n)

空間複雜度:O(1)

Optimal

這題跟上一個解法的 two-pointer 概念相同,只是這邊利用 Swap 的方式,將兩個迴圈合併成一個。

時間複雜度:O(n)

空間複雜度:O(1)

解法範例

Go

Space Sub-Optimal
func moveZeroes(nums []int) {
    var n, numZeroes int = len(nums), 0
    for i := 0; i < n; i++ {
        if nums[i] == 0 {
            numZeroes++
        }
    }
    var ans []int
    for _, num := range nums {
        if num != 0 {
            ans = append(ans, num)
        }
    }
    for numZeroes > 0 {
        ans = append(ans, 0)
        numZeroes--
    }
    for i := 0; i < n; i++ {
        nums[i] = ans[i]
    }
}
Space Optimal, Operation Sub-Optimal
func moveZeroes(nums []int) {
    var lastNonZeroFoundAt int = 0
    for i := 0; i < len(nums); i++ {
        if nums[i] != 0 {
            nums[lastNonZeroFoundAt] = nums[i]
            lastNonZeroFoundAt++
        }
    }
    for i := lastNonZeroFoundAt; i < len(nums); i++ {
        nums[i] = 0
    }
}
Optimal
func moveZeroes(nums []int) {
    var lastNonZeroFoundAt int = 0
    for i, num := range nums {
        if num != 0 {
            nums[lastNonZeroFoundAt], nums[i] = num, nums[lastNonZeroFoundAt]
            lastNonZeroFoundAt++
        }
    }
}

JavaScript

Space Sub-Optimal
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
    const n = nums.length;
    let numZeroes = 0;
    for (let i = 0; i < n; i++) {
        numZeroes += nums[i] === 0 ? 1 : 0;
    }

    const ans = [];
    for (const num of nums) {
        if (num !== 0) {
            ans.push(num);
        }
    }
    while (numZeroes--) {
        ans.push(0);
    }
    nums.splice(0, nums.length, ...ans);
};
Space Optimal, Operation Sub-Optimal
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
    let lastNonZeroFoundAt = 0;
    for (const num of nums) {
        if (num !== 0) {
            nums[lastNonZeroFoundAt++] = num;
        }
    }
    while (lastNonZeroFoundAt < nums.length) {
        nums[lastNonZeroFoundAt++] = 0;
    }
};
Optimal
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
    let lastNonZeroFoundAt = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== 0) {
            [nums[lastNonZeroFoundAt], nums[i]] = [nums[i], nums[lastNonZeroFoundAt]];
            lastNonZeroFoundAt++;
        }
    }
};

Kotlin

Space Sub-Optimal

Kotlin 的 Array 太多樣了,不太熟悉,所以就沒寫了


Space Optimal, Operation Sub-Optimal
class Solution {
    fun moveZeroes(nums: IntArray): Unit {
        var lastNonZeroFoundAt = 0

        for (num in nums) {
            if (num != 0) {
                nums[lastNonZeroFoundAt++] = num
            }
        }

        for (i in lastNonZeroFoundAt until nums.size) {
            nums[i] = 0
        }
    }
}
Optimal
class Solution {
    fun moveZeroes(nums: IntArray): Unit {
        var lastNonZeroFoundAt: Int = 0
        for (i in nums.indices) {
            if (nums[i] != 0) {
                nums[lastNonZeroFoundAt] = nums[i].also { nums[i] = nums[lastNonZeroFoundAt] }
                lastNonZeroFoundAt++
            }
        }
    }
}

PHP

Space Sub-Optimal
class Solution
{

    /**
     * @param Integer[] $nums
     * @return NULL
     */
    function moveZeroes(&$nums)
    {
        $n = count($nums);

        $numZeroes = 0;
        for ($i = 0; $i < $n; $i++) {
            if ($nums[$i] == 0) {
                $numZeroes++;
            }
        }

        $ans = array();
        foreach ($nums as $num) {
            if ($num != 0) {
                $ans[] = $num;
            }
        }

        while ($numZeroes > 0) {
            $ans[] = 0;
            $numZeroes--;
        }

        for ($i = 0; $i < $n; $i++) {
            $nums[$i] = $ans[$i];
        }
    }
}
Space Optimal, Operation Sub-Optimal
class Solution
{

    /**
     * @param Integer[] $nums
     * @return NULL
     */
    function moveZeroes(&$nums)
    {
        $lastNonZeroFoundAt = 0;
        foreach($nums as $num) {
            if ($num != 0) {
                $nums[$lastNonZeroFoundAt++] = $num;
            }
        }
        while ($lastNonZeroFoundAt < count($nums)) {
            $nums[$lastNonZeroFoundAt++] = 0;
        }
    }
}
Optimal
class Solution
{

    /**
     * @param Integer[] $nums
     * @return NULL
     */
    function moveZeroes(&$nums)
    {
        $lastNonZeroFoundAt = 0;
        for ($i = 0; $i < count($nums); $i++) {
            if ($nums[$i] != 0) {
                $tmp = $nums[$lastNonZeroFoundAt];
                $nums[$lastNonZeroFoundAt] = $nums[$i];
                $nums[$i] = $tmp;
                $lastNonZeroFoundAt++;
            }
        }
    }
}

Python

Space Sub-Optimal
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)

        # Count the zeroes
        num_zeroes = 0
        for i in range(n):
            num_zeroes += nums[i] == 0

        # Make all the non-zero elements retain their original order.
        ans = list()
        for num in nums:
            if num != 0:
                ans.append(num)

        # Move all zeroes to the end
        while num_zeroes > 0:
            ans.append(0)
            num_zeroes -= 1

        # Combine the result
        for i in range(n):
            nums[i] = ans[i]
Space Optimal, Operation Sub-Optimal
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        last_non_zero_found_at = 0
        # If the current element is not 0, then we need to
        # append it just in front of last non 0 element we found.
        for num in nums:
            if num != 0:
                nums[last_non_zero_found_at] = num
                last_non_zero_found_at += 1

        # After we have finished processing new elements,
        # all the non-zero elements are already at beginning of array.
        # We just need to fill remaining array with 0's.
        for i in range(last_non_zero_found_at, len(nums)):
            nums[i] = 0
Optimal
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        last_non_zero_found_at = 0
        for (i, num) in enumerate(nums):
            if num != 0:
                nums[last_non_zero_found_at], nums[i] = (
                    nums[i],
                    nums[last_non_zero_found_at],
                )
                last_non_zero_found_at += 1

Rust


Swift

Space Sub-Optimal
class Solution {
    func moveZeroes(_ nums: inout [Int]) {
        let n: Int = nums.count

        var numZeroes: Int = 0
        for i in 0..<n {
            if nums[i] == 0 {
                numZeroes += 1
            }
        }

        var ans: [Int] = []
        for num in nums {
            if num != 0 {
                ans.append(num)
            }
        }

        while numZeroes > 0 {
            ans.append(0)
            numZeroes -= 1
        }

        nums = ans
    }
}
Space Optimal, Operation Sub-Optimal
class Solution {
    func moveZeroes(_ nums: inout [Int]) {
        var lastNonZeroIndex: Int = 0
        for num in nums {
            if num != 0 {
                nums[lastNonZeroIndex] = num
                lastNonZeroIndex += 1
            }
        }

        while lastNonZeroIndex < nums.count {
            nums[lastNonZeroIndex] = 0
            lastNonZeroIndex += 1
        }
    }
}
Optimal
class Solution {
    func moveZeroes(_ nums: inout [Int]) {
        var lastNonZeroIndex: Int = 0
        for (i, num) in nums.enumerated() {
            if num != 0 {
                let tmp = nums[lastNonZeroIndex]
                nums[lastNonZeroIndex] = num
                nums[i] = tmp
                lastNonZeroIndex += 1
            }
        }
    }
}

Did you find this article valuable?

Support 攻城獅 by becoming a sponsor. Any amount is appreciated!