主題
題目連結(jié)：
題目意譯：
給定一非遞減排序之整數(shù)陣列 nums ，回傳非遞減之排序陣列，其元素為 nums 之元素之平方。
限制：
1 ≦ nums.length ≦ 10 ^ 4
-10 ^ 4 ≦ nums[i] ≦ 10 ^ 4
nums 按照非遞減之順序排序。
進(jìn)階： 將每個(gè)元素平方後再排序新的陣列是非常直觀的，那你可以找到一個(gè) O(n) 的解法嗎？
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： nums = [-4,-1,0,3,10]
輸出： [0,1,9,16,100]
解釋： 平方後，陣列變?yōu)?[16,1,0,9,100]。排序後，變?yōu)?[0,1,9,16,100]。
範(fàn)例 2：
輸入： nums = [-7,-3,2,3,11]
輸出： [4,9,9,49,121]
解題思維：
先找到第一個(gè) ≧ 0 的數(shù)字（如果有的話），將原陣列分為非負(fù)整數(shù)部分以及負(fù)整數(shù)部分（這部分請(qǐng)反轉(zhuǎn)）。例如 [-4,-1,0,3,10] 會(huì)變?yōu)?[0,3,10] 以及 [-1,-4]。
將兩者分開後，可以發(fā)現(xiàn)兩者元素平方（接續(xù)上例）：
[0,9,100]
[1,16]
兩者各自恰好為已按照非遞減之順序所排序。
因此接著我們可以按照合併排序（Merge Sort）之精神（因?yàn)闆]有直接講解過合併排序，但是有類似的，如這題），將兩子陣列合併即得到所求陣列。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
達(dá)人
