主題

LeetCode - 977. Squares of a Sorted Array 解題心得

Not In My Back Yard | 2021-02-27 00:00:01 | 巴幣 0 | 人氣 12

題目連結:


題目意譯:
給定一非遞減排序之整數陣列 nums ,回傳非遞減之排序陣列,其元素為 nums 之元素之平方。

限制:
1 ≦ nums.length ≦ 10 ^ 4
-10 ^ 4 ≦ nums[i] ≦ 10 ^ 4
nums 按照非遞減之順序排序。

進階: 將每個元素平方後再排序新的陣列是非常直觀的,那你可以找到一個 O(n) 的解法嗎?



範例測資:
範例 1:
輸入: nums = [-4,-1,0,3,10]
輸出: [0,1,9,16,100]
解釋: 平方後,陣列變為 [16,1,0,9,100]。排序後,變為 [0,1,9,16,100]。

範例 2:
輸入: nums = [-7,-3,2,3,11]
輸出: [4,9,9,49,121]


解題思維:
先找到第一個 ≧ 0 的數字(如果有的話),將原陣列分為非負整數部分以及負整數部分(這部分請反轉)。例如 [-4,-1,0,3,10] 會變為 [0,3,10] 以及 [-1,-4]。

將兩者分開後,可以發現兩者元素平方(接續上例):
[0,9,100]
[1,16]
兩者各自恰好為已按照非遞減之順序所排序。

因此接著我們可以按照合併排序(Merge Sort)之精神(因為沒有直接講解過合併排序,但是有類似的,如這題),將兩子陣列合併即得到所求陣列。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作