Java 白板題 把整數陣列中的0往後排，其餘維持原順序

去美商訊能集思Synergies駐點面試的白板題。給一整數陣列，並把陣列中的0移到最後，其餘的數字保持原來的順序。

例如輸入陣列{9, 0, 0, 3, 0, 0, 0, 1, 0, 4}，
請寫個方法可輸出為{9, 3, 1, 4, 0, 0, 0, 0, 0, 0}。

剛開始想用一個迴圈去遍歷陣列，若值不為0則放到另一個長度一樣的陣列中。

但接著要求不能使用另個陣列來裝，那意思就是只能在同個陣列進行操作。想了想大概也是元素互換位置的方法，因為之前做過「LeetCode Reverse String 字串反轉」 ，概念類似。

面試當下雖然知道大概的解法，但平時沒練習白板題很容易腦中一片空白。只能說面試這件事真的需要特別練習和準備（例如刷LeetCode），幾次面試下來都有這種體會，光靠平日的工作經驗是無法應付的。

public class Main {

    public static void main(String[] args) {

        int[] ints = new int[]{9, 0, 0, 3, 0, 0, 0, 1, 0, 4};

        int[] result = method3(ints);

        String resultString = toString(result);

        assert "9314000000".equals(resultString);

    }

    static int[] method1(int[] ints) {
        int[] result = new int[ints.length];
        int i = 0;
        for(int n : ints) {
            if (n != 0) {
                result[i] = n;
                i++;
            }
        }

        return result; // remain element will be 0
    }

    static int[] method2(int[] ints) {
        for (int i = 0 ; i < ints.length ; i++ ) {
            int n = ints[i];
            if (n != 0) continue;

            int j = 1;
            int m = 0;
            do {
                if (i + j == ints.length) break;
                m = ints[i + j];
                j++;
            } while (m == 0);
            // swap
            ints[i] = m;
            ints[i + j - 1] = n; // n is 0
        }

        return ints;
    }

    static int[] method3(int[] arr) {

        int c = -1;

        for (int i = 0; i < arr.length; i++) {

            if (arr[i] == 0 && c == -1) {
                c = i;
            }
            if (arr[i] != 0 && c != -1) {
                // swap
                int temp = arr[i];
                arr[i] = arr[c];
                arr[c] = temp;
                if (i - c > 1) {
                    c++; // 代表還有很多0, 往下進一個就好
                } else {
                    c = i;  // 代表只有他一個 0
                }

            }

        }
        return arr;
    }

    static int[] method4(int[] arr) {
        int idx = 0;
        for(int i = 0; i < arr.length; i++) {
            if (arr[i] != 0) {
                arr[idx++] = arr[i];
            }
        }

        while (idx < arr.length) {
            arr[idx++] = 0;
        }
        return arr;
    }

    static String toString(int[] array) {
        StringBuilder sb = new StringBuilder();
        for (int n : array) {
            sb.append(n);
        }
        return sb.toString();
    }

}

第一個方法method1()時間複雜度O(N)，空間複雜度O(2N)。

第二個方法method2()時間複雜度最糟是O(N²)，空間複雜度O(1)。

第三個方法method3()改自於下面我同事的JavaScript，時間複雜度O(N)，空間複雜度O(1)。

第四個方法method4()是前同事的答案的，時間複雜度O(2N)，空間複雜度O(1)。

和同事討論這題目，非常有趣，他睡覺時候想到了以下答案，時間複雜度O(N)，空間複雜度O(1)，真是聰明。不過因為同事習慣用JavsScript，所以下面是JavaScript的程式。還有同事不愛else寫法，所以我原汁原味照搬上來。

let arr = [9, 1, 10, 5, 0, 0, 3, 3, 3, 0, 0, 3, 0, 0, 0, 1, 0, 4]
let closed_index = null
for (let i = 0; i < arr.length; i++) {
    if (arr[i] === 0 && closed_index === null) {
        closed_index = i
    }
    if (arr[i] !== 0 && closed_index !== null) {
        // swap
        let temp = arr[i]
        arr[i] = arr[closed_index]
        arr[closed_index] = temp
        if (i - closed_index > 1) {
            // 代表還有很多 0, 往下近一個就好
            closed_index++;
        } else {
            // 代表只有他一個 0
            closed_index = i;
        }
        
    }
}
console.log(arr);

從這個問題中學到一個很重要的解題技巧，也就是雙指針，衍伸出技巧的就是滑動視窗(sliding windows)，此技巧常用來解決同一陣列內操作的問題讓時間複雜度限制在N內。

面試當天下著超大的雨，心得是我只是來駐點的考這個也太難了。後來又有第二次與資深工程師的面試就輕鬆許多，只問些工具的使用經驗而已，不過最終因對工作內容沒興趣及進公司要搭一個恐怖老舊電梯上去所以沒去駐點。

後來才知道這題是LeetCode 283. Move Zeroes。