LeetCode 283. Move Zeroes

Easy題。把陣列中的0往後移，其餘非0值維持原來的順序。解題時不可複製到新陣列，必須在同陣列中操作。

題目

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 <= 104
-231 <= nums[i] <= 231 - 1

先想到的解法

直覺想到用迴圈從頭往後一個一個檢查，如果是0則用另一個迴圈檢查後面是否有非0的值，若有則倆倆互換。內外兩廽圈時間複雜度O(n^2)，沒產生新陣列空間複雜度O(1)。

nums=[0,1,0,3,12]
==============================outter:L1, inner:L1=============================
      v(i=0)
nums=[0,1,0,3,12]
      ^(j=i)

==============================outter:L1, inner:L2=============================
      v(i=0)
nums=[0,1,0,3,12]
        ^(j=i+1)

swap nums[i] and nums[j]

      v(i=0)
nums=[1,0,0,3,12]
        ^(j=i+1)

==============================outter:L2, inner:L1=============================
        v(i=1)
nums=[1,0,0,3,12]
        ^(j=i)

==============================outter:L2, inner:L2=============================
        v(i=1)
nums=[1,0,0,3,12]
          ^(j=i+1)

==============================outter:L2, inner:L3=============================
        v(i=1)
nums=[1,0,0,3,12]
            ^(j=i+2)

swap nums[i] and nums[j]

        v(i=1)
nums=[1,3,0,0,12]
            ^(j=i+2)

==============================outter:L3, inner:L1=============================
          v(i=2)
nums=[1,3,0,0,12]
          ^(j=i)

==============================outter:L3, inner:L2=============================
          v(i=2)
nums=[1,3,0,0,12]
            ^(j=i+1)

==============================outter:L3, inner:L3=============================
          v(i=2)
nums=[1,3,0,0,12]
               ^(j=i+2)

swap nums[i] and nums[j]

          v(i=2)
nums=[1,3,12,0,0]
               ^(j=i+2)

Main.java

package com.abc.demo;

import java.util.Arrays;

public class Main {

    public static void main(String[] arges) {
        System.out.println(Arrays.toString(moveZeroes(new int[]{0, 1, 0, 3, 12})));
    }

    public static int[] moveZeroes(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                for (int j = i; j < nums.length; j++) {
                    if (nums[j] != 0) {
                        int tmp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = tmp;
                        break;
                    }
                }
            }
        }
        return nums;
    }

}

在LeetCode上提交後效能排名很後面，代表有更加解法。

更加解 一

用迴圈遍歷陣列及用一個佇列(queue)來記住元素0的索引。當遍歷到下次非0元素時將目前元素值放到queue中最前的索引位置，而目前元素值改為0。時間複雜度O(n)；用了一個最大同陣列長度的queue，空間複雜度O(n)。

nums=[0,1,0,3,12]
============================L1=============================
      v(i=0)
nums=[0,1,0,3,12]
q=[0]

============================L2=============================
        v(i=1)
nums=[0,1,0,3,12]
q=[0]

num[0] = num[i]
set num[i] = 0
q=[]

        v(i=1) 
nums=[1,0,0,3,12]
q=[1]

============================L3=============================
          v(i=2)
nums=[1,0,0,3,12]
q=[2,1]

============================L4=============================
            v(i=3)
nums=[1,0,0,3,12]
q=[2,1]

num[1] = num[i]
set num[i] = 0
q=[2]

            v(i=3) 
nums=[1,3,0,0,12]
q=[3,2]

============================L5=============================
               v(i=4)
nums=[1,3,0,0,12]
q=[3,2]

num[2] = num[i]
set num[i] = 0
q[3]

               v(i=4) 
nums=[1,3,12,0,0]
q=[4,3]

Main.java

package com.abc.demo;


import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class Main {

    public static void main(String[] arges) {
        System.out.println(Arrays.toString(moveZeroes(new int[]{0, 1, 0, 3, 12})));
    }

    public static int[] moveZeroes(int[] nums) {
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                q.add(i);
            }
            if (nums[i] != 0) {
                if (q.isEmpty()) {
                    continue;
                }
                nums[q.poll()] = nums[i];
                nums[i] = 0;
                q.add(i);
            }
        }
        return nums;
    }

}

更加解 二

參考網路解答。用廽圈遍歷陣列並紀錄最前元素0的索引及紀錄出現0的次數。當遍歷的元素非0時將紀錄元素0的索引位置的值設為當前元素值，並累加最前元素0的索引值到結束，最後從陣列尾端往前依出現0的次數依序把後面的元素值改為0。時間複雜度兩個單迴圈O(2n)相當於O(n)，空間複雜度O(1)。

nums=[0,1,0,3,12]
============================L1=============================
      v(i=0)
nums=[0,1,0,3,12]

firstZeroIndex=0
zeroCount=1

============================L2=============================
        v(i=1)
nums=[0,1,0,3,12]

set nums[0] = nums[i]

        v(i=1)
nums=[1,1,0,3,12]

firstZeroIndex=1
zeroCount=1

============================L3=============================
          v(i=2)
nums=[1,1,0,3,12]

firstZeroIndex=1
zeroCount=2

============================L4=============================
            v(i=3)
nums=[1,1,0,3,12]

set nums[1] = nums[i]

            v(i=3)
nums=[1,3,0,3,12]

firstZeroIndex=2
zeroCount=2

============================L5=============================
               v(i=4)
nums=[1,1,0,3,12]

set nums[2] = nums[i]

               v(i=4)
nums=[1,3,12,3,12]

firstZeroIndex=3
zeroCount=2

============================Loop End=============================

Set the last 2 elements to 0

nums=[1,3,12,0,0]

Main.java

package com.abc.demo;


import java.util.Arrays;

public class Main {

    public static void main(String[] arges) {
        System.out.println(Arrays.toString(moveZeroes(new int[]{0, 1, 0, 3, 12})));
    }

    public static int[] moveZeroes(int[] nums) {
        int i = 0;
        int firstZeroIndex = 0; // 最前元素0的索引
        int zeroCount = 0; // 紀錄元素0的出現次數
        while (i < nums.length) {
            if (nums[i] != 0) {
                nums[firstZeroIndex] = nums[i];
                firstZeroIndex++;
            } else {
                zeroCount++;
            }
            i++;
        }

        // 從陣列後往前依照0出現次數依序把元素值改為0
        for (int j = nums.length - 1; j >= nums.length - zeroCount; j--) {
            nums[j] = 0;
        }

        return nums;
    }

}

寫完想起來兩年前去美商訊能集思駐點面試時考過這題白板題。