LEETCODE 解題紀錄 #3
954. Array of Doubled Pairs
└─解題難度：MEDIUM
熱騰騰的今日題。
題目說明
給定一個陣列 arr ，判斷 arr 若經過適當調整順序後，對所有 0 ≤ i < len(arr)/2 是否可滿足 arr[2*i+1] = 2*arr[2*i]。
舉個簡單的例子，arr=[4,-2,2,-4] ，我們可將 arr 調整為 [2,4,-2,-4] 或 [-2,-4,2,4]即滿足題目給定的條件，因此返回 true。
若以首項索引為 0，我們可以一句話總結題目要求：若經適當調整順序後，判斷奇數項的值是否均為其前一偶數項的值的兩倍。
解題思路
從題目的 arr[2*i+1] = 2*arr[2*i] 這個條件中，我們可以將陣列裡的元素視為兩兩配對 (arr[2*i], arr[2*i+1])。在後續的討論中，我會將 arr[2*i] 稱為配對的左值，arr[2*i+1] 稱為右值──所有右值皆為左值的兩倍。
當我們遇到任一元素，若我們知道此元素為左值或右值，我們就可以計算它的配對值──對左值來說我們將其乘二即為右值、對右值來說我們將其除二──並在陣列中尋找其配對值是否存在，從而判定陣列是否即為所求。
然而我們無法完全肯定一個元素是否為左值或右值，我們只有幾個線索。
- 0 的左值或右值都是 0。0 只能和 0 配對，也不會有其他不為 0 的元素和 0 配對。
- 絕對值最小的元素必為左值。我們可以透過反證法來證明：假若一元素 a 為陣列中絕對值最小且不為 0 的元素且為右值，則其左值為 a/2，但 |a| > |a/2|，a 不可能為絕對值最小之元素，因此證偽──絕對值最小的元素可為右值的假設不成立，因此必為左值。
- 奇數必為左值。因為右值必為偶數，它是左值的兩倍。
- 左值和右值同除一不為 0 的值之後配對關係仍成立。即同除後仍滿足
arr[2*i+1] = 2*arr[2*i]。
從官方的解法和討論區中看到大部分的解法都是基於線索 2。
在這種解法中，我們須對陣列按絕對值進行排序 (時間複雜度 O(N logN))，並從最小的元素開始，令其為左值並確認右值存在，每當配對兩個值就將其自陣列中移除，並持續尋找最小元素值到找不到配對值或是陣列為空 (時間複雜度 O(N))。
整體來說，因為排序的關係，時間複雜度為 O(N logN)，空間複雜度可以達到 O(1)。
解法方案
我的方法主要是基於線索 3 ──奇數必為左值。
每個循環 (L18 — L35) 分為兩個階段：
- 尋找所有奇數值及其右值，並將其自陣列中剔除。若找不到配對值，立即返回 false 表示配對失敗。
- 將陣列所有元素除以二並回到階段 1。因為此時陣列內的奇數和部分偶數都被剔除了，必只剩下偶數。基於線索 4，我將陣列所有元素同除 2，配對關係仍然成立。
在程式碼中可以發現我有個變數 counters 為 Map 的資料結構，此結構的鍵為陣列的元素值 arr[i]，值為 arr[i] 在陣列中出現的次數。若出現次數為 0，則將該鍵刪除。counters 的目的是為了將尋找、刪除元素的動作由 O(N) 降為 O(1)。
由上述兩階段一直循環到 counters 大小為 0，即陣列已經被我們檢查完畢。
複雜度分析
這邊的時間複雜度我個人覺得比較難分析，如果有分析錯誤請務必提醒我。
每個數字只會自陣列中被剔除一次，在它被剔除之前，它可能會歷經數次除以 2 的過程，因此最壞狀況便是 log M 次，其中 M 表示陣列中所有左值的最大絕對值。
總共為 N 個元素，因此演算法時間複雜度為 O(N log M)。
這個演算法最佳的狀況是在所有左值皆為奇數時，時間複雜度為 O(N)。
若考慮到題目給定的值域限制：
2 ≤ arr.length ≤ 3 * 10⁴-10⁵ ≤ arr[i] ≤ 10⁵
N 的最大值為 3 * 10⁴ ，M 的最大值為 5 * 10⁴，因此在最壞狀況中，我的解法會比官方解法 (帶排序的方法) 慢一點。
但我的方法因為是過程中即時判斷是否符合配對條件，一有不合立刻返回 false，而官方解法 (帶排序的方法) 則須先行排序後才能開始判斷，因此我認為在平均狀況中，我的方法會略快於官方解法 (帶排序的方法)。
這是八月挑戰的今日題解題，歡迎各位與我一起寫題，我們下次見！
