# 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.

## 解法解析

### Space Sub-Optimal

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

### Space Optimal, Operation Sub-Optimal

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

### 解法範例

#### 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
}
}
}
}
``````