刷題筆記 — Array (1)
本系列文章是分享我在 Leetcode 及 Algoexpert 的刷題經驗，此篇文章是 Array 篇的第一篇文章。
本系列文章都假定讀者具有基礎的 complexity analysis 概念以及基礎的 Java 能力。為了不讓閱讀時間過長，每篇都只會講解 3 道題目。
每道題目我都會分為 Description(問題描述)、Examples(測資範例)、Solution(解法)、Implementation(實作) 等區塊來進行講解。但如果該解法比較不理想（太複雜、效率太差）我可能就只會進行概念上的講解，並不會實際寫出 code implementation。
另外，為了讓讀者能更佳地了解，當我提及程式碼的變數時，我會將該字反白（如 variable ）。
如欲觀看所有系列文章，可點下面連結前往。
https://medium.com/citychaser/coding-questions/home
好了，廢話不多說，讓我們開始吧！
1. Squares of a Sorted Array
Description
給定一個 array of integers nums，裡面元素為 non-decreasing 排列，需回傳一個 array 以 non-decreasing 排列平方後的元素。
Examples
Input: [-4, -1, 0, 3, 10]
Output: [0, 1, 9, 16, 100]Solution 1 — Brute Force
這題最簡單但也最暴力的解法就是先迭代 nums 得出平方後的 array（以範例來說就是 [16, 1, 0, 9, 100]），然後再 sort 這個 array。
但如果我們這麼做的話，sort 本身會需要 O(NlogN)的 time complexity（大部分程式語言內建的 sorting algorithm 是採用 merge sort / heap sort based 的 algorithm，所以 time complexity 接近於 O(NlogN)）。
所以如果我們採用這個解法，time complexity 會是 O(NlogN) 。
Solution 2 — Two Pointer
在說明第二個解法之前，我們先來看看標題這個 two pointer 是什麼意思，所謂 two pointer 是在 array-like 的問題中常常使用到的一個解題技巧，意指使用兩個指標來「同時」指到 array 中的兩個位置，並透過這兩個位置中元素的關係去做出不同的動作。這邊的 pointer 並不是指 programming language 中的資料結構，只是一種概念而已，當然你也可以實際用 pointer 來存，但也可以只是一個紀錄 index 的 integer。
說完什麼是 two pointer 後，我們接著來看這題怎麼用它來解決。仔細查看題目，可以發現其實題目有給一個線索，那就是 non-decreasing，也就是說原本的 nums就是 sorted 的狀態。但我們不能直接將裡面的每個元素平方後就回傳，因為有些負數經過平方後可能會比正數的平方來得大，平方後負號會被消掉，所以單看數字大小決定誰大。
但是！如果仔細思索就會發現一件事，因為 nums 是 sorted，所以正、負數都是由小排到大，也就是說如果將 nums 裡的每個整數平方，那麼負數的部分會由大排到小、而正數的部分會由小排到大！
結合剛剛的 two pointer，你有想到怎麼將這兩個線索結合了嗎？我們將 pointer 分別指到 nums 的第一個跟最後一個元素 ，分別是負數/正數平方後最大的數（假設為 a、 b）。如果 a² 的平方比較大，那就把 a² 塞在新的要回傳的 array 最後面；如果是 b² 比較大，那就把 b² 塞在新的要回傳的 array 最後面，接著被塞進去的那邊就往中間一格，如此重複下去直到所有元素都已經被塞到新的 array。
這麼說有點模糊，我們舉個實例。想像有兩組人，兩組都按身高從高排到低，一開始看兩邊最高的人誰高，假設第一排最高的人比較高，就把他叫去第三排當第一個，然後再接著比較第一排第二高的人跟第二排最高的人誰高，高的就叫他離開原本那排去第三排接著排隊，以此類推直到所有人都排到第三排為止。
你可能會想，如果左邊的 pointer 在往右移的過程中，指到的數字變成正的；或是右邊的 pointer 在往左移的過程中，指到的數字變成負的怎麼辦？其實不影響，因為如果左邊的 pointer 指到正數，代表剩下的都是正數，所以右邊的 pointer 指到的數字接下來一定都比左邊指到的大，也就是說左邊的 pointer 接下來都不會移動了，反之亦然。
整個過程我們只有迭代 nums 一次，而且每次的操作都是 constant time，所以總 time complexity 為 O(N)。
但是因為這個解法需要額外的一個 array 來儲存，所以 space complexity 也會是 O(N) 。
2. Duplicate Zeroes
Description
給定一個 array of integers arr，將 array 裡面出現的每個 0 複製一次，並把所有元素往右移。如果超過 array 長度，則丟棄那些溢出的元素。
不可以另外建立新的 array 回傳，必須修改原有的 nums (in-place operation)。
Examples
Input: [1, 0, 2, 3, 0, 4, 5, 0]
Output: [1, 0, 0, 2, 3, 0, 0, 4]Solution 1 — Shifting
因為不能額外建立新的 array 去儲存，所以我們只能去修改原本的 array。可是麻煩的點就在，因為我們要 duplicate 0，這會導致 0 後面的元素被蓋掉。
要解決這問題，我們可以用變數去記住稍後會被蓋掉的元素，可是當 0 很多個或是連續出現好幾個的時候，我們就要提前去記住接下來很多個會被蓋掉的元素，邏輯會很複雜，也沒辦法預預測你必須要保留多少個會被蓋掉的變數，如此就要用 array-like 的資料結構去記，那就失去不能使用新的 array 這個限制的意義了。
仔細觀察後可以發現，一定是後面的元素會被前面的擠掉，不會是前面被後面擠掉，因為整個 array 是往右 shift 的。
我們也可以發現，只要有一個 0 出現，那就代表從 array 的尾巴會有一個元素被擠掉。所以，我們就從 array 的頭開始出發，每遇到一個 0，我們就把從這個 0 以後的所有元素往右一格，直到最後一個元素就行。
但是我們可以發現，裡面包了兩層的 for-loop，第一層是檢查每個元素是否為 0 ，第二層是將該位置以後的元素全部往右移一個。這樣下來的 time complexity 會是 O(N²)。
Solution 2 — Back Tracking
只要每出現一個 0，就代表它一個人要佔 array 中的兩格。因此我們只要先掃描一次 array，出現非 0 的元素就將已經被佔掉的格數 +1；出現 0 則+2，檢查到了哪個位置時，目前元素佔掉的格數已經等於或大於原本 array 的長度，我們就可以知道從這個位置開始，後面的都會因為溢出而不會被寫到 array 裡。然後，我們就從這個位置開始往 array 的頭回推，遇到 0 的話就填入兩個 0，不是 0 的話就填入該元素就好。
這麼說可能還是有點模糊，我們來看看下面這張示意圖。
因為我們已經算過到第幾個元素會是儲存的界限，所以你會看到，留下來的 array 中有幾個 0，就應該是這個留下來的 subarray 的長度跟初始 array 長度的差。（e.g. [1, 0, 2, 3, 0, 4] 長度為 6，有兩個 0，6+2 剛好會是初始 array [1, 0, 2, 3, 0, 4, 5, 0] 的長度。）
可以看到這個解法，只需要從頭迭代 arr 兩次（第一次找到哪裡開始會溢出，第二次將所有元素從後到前填完），所以 time complexity 只會是 O(N) 。
3. Merge Sorted Array
Description
給定兩個 array of integers nums1, nums2，其中 nums1 含有 m 個元素、 nums2 有 n 個元素，兩者皆為 sorted (in ascending order)。
將兩者合併成一個 sorted array (in ascending order)，必須將 nums2 合併到 nums1中，不可建立新的 array，也就是說 space complexity 必須為 O(1)。
另外，nums1 的長度為 m+n，但只有前 m 個元素為有值的元素，後面的 n 個為 0（非數字 0，而是代表空值）。
Examples
Input:
nums1 = [1, 2, 3, 0, 0, 0]
nums2 = [2, 5, 6]Output:
nums1 = [1, 2, 2, 3, 5, 6]
Solution 1 — Brute Force
最直觀也最暴力的方法便是把所有 nums2 元素先塞到 nums1 後面，然後再把整個 nums1 進行 sorting。
如果這麼做的話，首先把 nums2 塞進 nums1 會需要 n steps，而 sort nums1 則會需要 (m+n)*log(m+n) steps，因此總共的 time complexity 會是 O(n + (m+n)*log(m+n)) ，只留下領導項便是 O((m+n)*log(m+n)) ，蠻不理想的。
Solution 2 — Insert One Each Time
因為我們必須將 nums2 的元素給 merge 到 nums1 裡面，最直觀的解法大概是每次從 nums2 中取一個元素出來，然後從 nums1 的頭開始迭代，找到對應插入的位置後，將 nums1 該位置後的元素全部往右一格。
接著，繼續迭代下一個 nums2 元素，從插入上一個 nums2 元素的位置繼續往下比對，找到要插入的位置後，一樣把 nums1 該位置後的所有元素往右移一格，如此反覆操作直到 nums2 元素全部迭代完。
另外，其實在每次插入 nums2 元素時，可以檢查是不是插在所有 nums1 元素的後面了，如果是的話，就代表這個 nums2 的元素已經比所有 nums1 元素來得大，接下來就直接把剩下的 nums2 元素從這個位置往後依序排放即可。
迭代每個 nums2 元素共需要 n steps，而每個 nums2 元素要找到插入位置並把該位置後的元素右移需要 m+n steps，因此這個解法的 time complexity 是 O(n*(m+n)) ，雖然比上面的解法好，但還是有改善空間。
Solution 3 — Two Pointer
沒錯，又是 two pointer！這題可以怎麼利用 two pointer 呢？我們可以從題目的敘述中看到兩者都是 sorted，只要看到兩者都是 sorted，那就代表我們可以像上面第一題那樣，從兩邊最大 / 最小的開始兩兩比較，選出較大 / 小的放到，被選到的那邊就往下個元素走，如此兩兩比較到兩邊的元素都被選完。
而這題要從最小還是最大開始呢？答案是最大，因為題目說要把 nums2 merge 到 nums1 裡面，如果我們從最小的開始，那麼就會把 nums1 前面的元素蓋掉。但如果從最大的開始，就會從後面開始放，而 nums1 的長度是 m+n ，即便是把整個 nums2 塞進 nums1 的後面也不會覆蓋到 nums1 原本的元素。
因此我們兩兩比較，把較大的元素從後面開始往前擺，直到兩邊的元素都用完為止。總共有 m+n 輪要比較，所以 time complexity 只會是 O(m+n) ，乍看跟上面沒什麼太大差別，但當 m , n 非常大時，就差得非常多。e.g. m = 10000 , n= 10000 ， m*n = 10⁸、 m+n = 20000 = 2*10⁴。
今天的刷題分享就到這邊了，如果有什麼指教或是建議，歡迎在這篇文章底下留言；如果覺得這篇文章不錯，也歡迎給我點掌聲！
👉 下一篇：刷題筆記 — Array (2)
