刷題筆記 — Array (3)
本系列文章是分享我在 Leetcode 及 Algoexpert 的刷題經驗，這篇文章是 Array 篇的第三篇文章。
本系列文章都假定讀者具有基礎的 complexity analysis 概念以及基礎的 Java 能力。為了不讓閱讀時間過長，每篇都只會講解 3 道題目。
每道題目我都會分為 Description(問題描述)、Examples(測資範例)、Solution(解法)、Implementation(實作) 等區塊來進行講解。但如果礙於篇幅問題或是該解法比較不理想（太複雜、效率太差）我可能就只會進行概念上的講解，並不會實際寫出 code implementation。
另外，為了讓讀者能更佳地了解，當我提及程式碼的變數時，我會將該字反白（如 variable ）。
👉 上一篇：刷題筆記 — Array (2)
如欲觀看所有系列文章，可點下面連結前往。
https://medium.com/citychaser/coding-questions/home
好了，廢話不多說，讓我們開始吧！
1. Smallest Difference
Description
給定兩個 non-empty array of integers array1, array2，從兩個 array 中各自挑選一個整數，撰寫一個 function 回傳相減差距（絕對值）最小的一組。
產生最小值的組合只會有一組，不會有多組同時產生最小值的情形發生。
Examples
Input:
array1 = [-1, 5, 10, 20, 28, 3]
array2 = [26, 134, 135, 15, 17]Output:
[28, 26]
Solution 1 – Brute Force
最簡單、直觀的解法就是用 brute force 把每一組答案都試一次，找到最小的那組。
因為我們寫了兩層 for loop，總共有 N*M 個 operations，所以 time complexity 為 O(N*M)。
Solution 2 – Sorted Array with Two Pointer
沒錯！又是 two pointer！
將兩個 array 用 ascending order 進行 sorting 後，從兩者的開頭都選出第一個整數作為第一組。在檢查每一組的差距時，如果差距是 0，代表已經找到了，後面的都不用找了（因為最小的差距是 0，而且題目說只會有一組）；如果不是 0，我們就看是不是比目前的最小值還小，如果是的話，就更新最小值。
重點在接下來的步驟，我們找出兩者中比較小的整數，然後把指向它的 pointer 往後移，為什麼呢？
假設現在 array1 中被指到的整數是第三個，用 x_3 表示、array2 中被指到的整數是第四個，用 y_4 表示。如果 x_3 < y_4，x_1, x_2 都比 x_3 小，那麼它們跟 y_4 的差距只會更大；同理，y_5、y_6 … 跟 x_3 的差距也只會越來越大。所以我們要去移動比較小的那邊的 pointer，如此差距才有縮小的可能。
如此反覆進行，直到有一邊的 array 已經窮盡所有元素，那我們就可以停止了。
現在我們來看看 time complexity，首先，sorting 的部分各需要 O(NlogN) & O(MlogM)（假設使用 merge sort、quick sort based method）。
而下面找尋 minimum 的部分，最多我們只會執行 N+M-1 次的 operation，因為如果有一者的元素全部迭代完就結束了。
所以總共的 time complexity 會是 O(NlogN + MlogM + N + M — 1)，去掉低項，最後的 time complexity 會是 O(NlogN + MlogM)。
乍看起來好像沒有比 O(NM) 好，但是假如 N, M 都很大的時候就會差很多了，因為 log(N), log(M) 增長速度很慢，基本可以忽略。所以會是 N+M 與 N*M 的差距，兩者都很大的時候就差很多。
2. Monotonic Array
Description
給定一個 array of integers，判斷此 array 是否為 monotonic (單調)。
所謂 monotonic 即是非嚴格遞增/非嚴格遞減，也就是 X1 ≤ X2 ≤ … ≤ Xn 或 X1 ≥ X2 ≥ … ≥ Xn。
如果是空 array 或是 array 長度為一，也視為 monotonic。
Examples
Input: [-1, -5, -10, -1100, -1100, -1101, -1102, -9001]Output: true
Solution
這題該怎麼解呢？首先，單調有兩種：單調遞增＆單調遞減，所以我們必須要同時檢查這兩種。
當然你可以用兩次的 for-loop 去分別檢查是單調遞增還是單調遞減，但其實只要一次的 for-loop 就可以檢查完。
要怎麼檢查是遞增還是遞減呢？只要看下一個元素減掉目前的元素，如果是大於 0，代表後面的元素比較大，這兩者之間是「嚴格遞增」，注意！是嚴格遞增不是單調遞增；相反的，如果小於 0，代表後面的元素比較小，這兩者之間是「嚴格遞減」。
你可能覺得奇怪，不是要找單調遞增 / 遞減嗎？為什麼反而去檢查嚴格遞增 / 遞減呢？那是因為單調遞增的反面就是嚴格遞減，而單調遞減的反面就是嚴格遞增。所以只要我們發現 array 中有兩個元素成嚴格遞增，那就代表 array 一定不符合單調遞減；反之，如果有兩個元素成嚴格遞減，那就代表 array 一定不符合單調遞增。
於是我們假設 array 一開始同時符合單調遞增且單調遞減，接著去迭代 array，看看在這中間有沒有違反單調遞增 / 遞減的情形，如果有，我們就把對應的狀況設為 false。最後，只要兩者有一者是 true，那就代表這個 array 是 monotonic。
3. Next Permutation
Description
Permutation 意指「排列」，給定一個 array of integers array，將 array 中的整數更改成「依照字典順序的」下一個排列。
如果已經到「依照字典順序」的最後一個排列順序，則回到第一個排列順序。
所有的操作必須是 in-place，也就是必須更動原本的 array，不得建立並回傳一個新的 array。
Examples
Input: [1, 2, 3, 4]
Output: [1, 2, 4, 3]Input: [1, 1, 5, 4]
Output: [1, 4, 1, 5]Input: [4, 3, 2, 1]
Output: [1, 2, 3, 4]
Solution 1 – Brute Force
你當然可以使用 brute force 去算出所有組合，但仔細思考一下就會發現，如果有 N 個數字，就會有接近 N! 種組合，因此 time complexity 會是夢魘等級的 O(n!)，所以連考慮都不用考慮，畢竟 10! 就已經是 3628800 這種可怕的數字了，更不用說如果 N = 100，那會是個天文數字，可能跑好幾年還跑不出來。
Solution 2 – Trace Backwards
這題其實有個小 trick，如果沒有發現，那麼解起來將會非常困難。如果一個 sequence 是「降冪排列」，那麼就代表，已經沒有下一個「按字典順序」的排列了，必須從頭開始。
看個例子，9, 7, 7, 4, 3, 1 這個 sequence 是降冪排列，無法按照字典順序找到下一個排列，只能回到 1, 3, 4, 7, 7, 9。
掌握了這個性質後，我們只要從 sequence 的後面檢查回來，如果找到某個數字，從他開始不是降冪排列，那麼就代表這之後還有可以「照字典順序」排列的下一個 sequence，那麼我們就只需要從這之後去排列。
再看個例子，1, 2, 3, 7, 5, 4, 1，從後面找回來，可以發現到 3 的時候，sequence 不再是降冪排列（現在這個數字比上一個來得小），所以代表從 3 這個位置開始的 subsequence 還有往下按照字典排列的可能。
而按照字典排列的話，3 之後就是 4、如果沒有 4 那就是 5…以此類推，所以我們只要找到 3 以後比 3 大且跟 3 最接近的數字，然後把兩者對調。
原本 1, 2, 3, 7, 5, 4, 1，將會變成 1, 2, 4, 7, 5, 3, 1。
雖然把 3 的下一個與 3 對調了，但是可以發現，從原本 3（現在是 4）的位置後，並不是從小排到大，因為現在 3 的位置已經變成 4 了，所以後面的順序也要變成從最小的開始，所以後面的要由小排到大。
聽到由小排到大可不要馬上就一股腦兒的去 sort！其實我們可以發現剩下的 subsequence，他原本就是降冪排列，也就是本來就是 sort 過後的！只是我們現在要把降冪變成升冪，所以其實不用重新 sort 過一次，我們只要把它反過來排就好。
那要怎麼反過來呢？很簡單，只要把頭跟尾對調，然後一直往中間靠攏，直到所有數字都被對調過即可。
使用這個方法的 time complexity 為 O(N)，可以看到程式碼裡頭不管是 for-loop 還是 while-loop 都只有包一層而已，而且是以 array 的長度為界限。
我們也沒有使用額外的資料結構，所以 space complexity 為 O(1)。
今天的刷題分享就到這邊了，如果有什麼指教或是建議，歡迎在這篇文章底下留言；如果覺得這篇文章不錯，也歡迎給我點掌聲！
👉 下一篇：刷題筆記 — Array (4)
