刷題筆記 — Array (2)
本系列文章是分享我在 Leetcode 及 Algoexpert 的刷題經驗，此篇文章是 Array 篇的第二篇文章。
本系列文章都假定讀者具有基礎的 complexity analysis 概念以及基礎的 Java 能力。為了不讓閱讀時間過長，每篇都只會講解 3 道題目。
每道題目我都會分為 Description(問題描述)、Examples(測資範例)、Solution(解法)、Implementation(實作) 等區塊來進行講解。但如果礙於篇幅問題或是該解法比較不理想（太複雜、效率太差）我可能就只會進行概念上的講解，並不會實際寫出 code implementation。
另外，為了讓讀者能更佳地了解，當我提及程式碼的變數時，我會將該字反白（如 variable ）。
👉 上一篇：刷題筆記 — Array (1)
如欲觀看所有系列文章，可點下面連結前往。
https://medium.com/citychaser/coding-questions/home
好了，廢話不多說，讓我們開始吧！
1. Remove Element
Description
給定一個 array of integers nums 和一個 integer val，計算 nums1 中不等於 val 的個數有幾個（假設為 N），並且修改 nums，讓其前 N 個元素是那些不等於 val 的元素，後面的元素是什麼並不需要考慮。
此題必須要修改原有的 nums，不可額外建立新的 array 或其他 data structures，space complexity 必須為 O(1) 。
Examples
Input: nums = [3, 2, 2, 3], val = 3
Output: 2, nums = [2, 2, 3, 3]
# 只要前兩個是 2 就行，nums = [2, 2, 0, 0] 一樣也是正確答案Input: nums = [0, 1, 2, 2, 3, 0, 4, 2], val = 2
Output: 5, nums = [0, 1, 4, 0, 3] (這五個元素可用任何排列順序，只要保證所有不是 val 的元素都有在前 N 個位置即可)
Solution 1 — Two Pointer Swap
val 在 nums 裡面有 m 個，而 nums 總共有 n 個元素，我們要做的就是把不是 val 的元素放在 nums 的前 n-m 個。
要做到這件事，我們可以使用兩個 pointer，分別從頭尾兩端往內走（以下稱為 head, tail），因為我們要把等於 val 的元素往後送、不等於 val 的元素往前送，所以當 head 指到的元素是 val 且 tail 指到的元素不是 val 時，我們就把兩者互換。
如果上面條件不成立的話，那還要再根據兩個條件判斷一次。如果 head 指到的元素是 val，那 head 不能繼續往後走，要等 tail 指到不是 val 的元素時要互換；但如果 head 指到的元素不是 val，那就繼續往後走。 而 tail 則跟 head 相反，指到不是 val 的元素時要停下來，否則繼續往前。
Solution 2 — Two Pointer Override
題目其實有提到，只需要讓不等於 val 的元素在 nums 的前 n-m 個就可以，後面的元素是什麼其實不重要。
因此，我們可以利用一個比上面更好的方法來解決這題。
我們一樣使用兩個 pointer p1, p2，兩者初始時都指到 nums 的第一格。如果 p2 指到的元素不是 val，那就把值 assign 給 p1 所在的那格。接著，兩者都往後一格；如果 p2 指到的元素是 val，那就把 p2 往後移一格。
這個解法乍聽下來不知道為什麼可以 work，但其實很簡單， p2 從 nums 第一格一直往後，最終會迭代每一個元素。當它指到的元素不是 val 時，就會把這個值往前塞，總共會塞幾次？答案是 n-m 次，因為 nums 總共有 n 個元素，其中有 m 個等於 val，所以不等於 val 的就是 n-m。而 p1 一開始也是指到 nums 第一格（index 為 0），它只有在 p2 指到的元素不是 val 時才會將指到的該格往下，總共會進行 n-m 次，所以會將 nums 前 n-m 格換成不是 val 的元素，而且不會有重複的問題，因為 p2 只會指到每個元素一次。
以上兩個解法的 time complexity 其實都是 O(n) ，不過第二個解法概念上更為簡潔，也不用處理 edge case 的問題。
2. Replace Elements with Greatest Element on Right Side
Description
給定一 array of integer arr，將每個元素替換成該元素右邊所有元素中最大值，最後一個元素則替換成 -1。
Examples
Input: arr = [17, 18, 5, 4, 6, 1]
Output: [18, 6, 6, 6, 1, -1]Solution 1 — Look Right Every Time
既然要找右邊最大的元素，那麼最簡單的方法就是每當迭代到某個元素時，就從他下一個開始找到 arr 的最後一個，看最大的是誰。每個元素都重複這個動作，直到倒數第二個元素，最後一個則直接置換成 -1 。
雖然簡單明瞭，但是可以想見，這個解法的 time complexity 不會太好，因為它疊了兩層的 for-loop，第一層先迭代每個元素，第二層又要從該元素的右邊一格一直找到最後一格。總共的 time complexity 會是 O(N²)，是一個 brute force 的解法。
Solution 2 — Trace Backwards
有沒有辦法只迭代一次 arr 就完成這項任務呢？是可以的！我們只要從最後面開始就辦得到。
如果從前面開始的話會遇到一個問題，第一次迭代整個 arr 我們可以找到最大值，但這個最大值不能應用到所有元素身上，因為隨著往右走的過程中，會越過這個成為最大值的元素，而在這個最大值右邊的元素，它們右邊的最大值就不會是整個 arr 的 global maximum 了，於是又要針對每個元素重新去找。
但如果從末端開始就不會有這個問題，從末端往前找的過程中一直紀錄著目前找到的最大值，到了某個位置時，我們先將該位置替換成目前的最大值，除此之外，還要檢查這個元素是不是大於目前的最大值，如果是的話，就要把最大值替換成這個元素。
在這個解法中，我們只將 arr 所有的元素迭代一次，在每個元素的操作中也都是 constant time operation，因此總共的 time complexity 為 O(N) 。
我分別將這兩個解法都 submit，前者花了 143ms 的 runtime，後者只花了 1ms，可見差別是非常大的。
3. Sort Array by Parity
Description
給定一個 array A，裡面的每個元素都為 non-negative integers，回傳一個 array，其中出現在 A 中的所有偶數元素必須排列在所有奇數元素前面（不用考慮偶數與偶數間、奇數與奇數間的順序）。
Examples
Input: [3, 1, 2, 4]
Output: [2, 4, 1, 3] / [2, 4, 3, 1] [4, 2, 1, 3] / [4, 2, 3, 1] (四組皆為正確答案)Solution 1 — Two Pointer with New Array
建立一個新的 array B，長度與 A 相同，接著 loop through A，遇到奇數的時候放到 B 的尾端，並且把尾端往左一格；遇到偶數的時候放到 B 的頭端，並且把頭端往右一格，直到迭代完 A 的所有元素。
這個解法的 time complexity 為 O(N)，但是因為我們使用了額外的 array，因此 space complexity 也為 O(N)。
Solution 2 — Two Pointer without New Array
上面的解法是將兩個 pointer 放在「新的」array，而這個解法則是將兩個 pointer 放在原 array A 的頭 (head) 與尾 (tail)。我們的目標是要將偶數全部放到前面、奇數全部放到後面，所以也就是說，當 head 遇到奇數時，應該要把它往後丟、當 tail 遇到偶數時，應該要把它往前丟。
所以當這兩個條件都成立的時候，我們就把兩者位置互換，讓奇數去後面、後數去前面。那如果只有一個條件成立呢？那就是讓條件不成立的那個 pointer 繼續往中間移動，直到兩個條件成立。什麼時候會停？當兩個 pointer 交會的時候就停下來。
今天的刷題分享就到這邊了，如果有什麼指教或是建議，歡迎在這篇文章底下留言；如果覺得這篇文章不錯，也歡迎給我點掌聲！
👉 下一篇：刷題筆記 — Array (3)
