從LeetCode學演算法

0977. Squares of a Sorted Array (Easy)

Question

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1

1
2
Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 2

1
2
Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A is sorted in non-decreasing order.

分析/解題

給定一個非遞減排序(也就是相等或遞增)的陣列，
以排序好的狀況回傳其每個元素平方後所得的陣列。

一般我們所熟知的排序應該需要至少O(NlogN)的狀況才能達成，
(之後筆者會再挑一題來專門作排序這個部分的問題)
但這題在平方過以後，並不算完全散亂的狀態，
原先負整數的部分平方後會由大到小排列 ；
原先0到正整數的部分平方後則會由小到大排列 。
利用這點我們可以使用two pointer的模式來進行處理，
每次將兩邊的元素絕對值進行比較，比較大的代表其平方後比較大，
將其取出置於新的陣列/串列的最右邊，依序往回填。

實作上，如果不限制A必須保持原樣的話，
也可以先將負號的部分全數去掉，再進行後面的比較時，
就可免去取絕對值了。

Java的部分兩個方法皆有提供，讀者可依實際狀況決定寫法。

Java

Python的部分，還另外提供了一個偷吃步的方法：
使用sorted函式搭配list comprehension，一行即可解決問題，
但其時間複雜度為O(NlogN) (因為直接使用排序法)

神奇的是，這個方法還比較快XD
(估計是A的長度限制在比較小的範圍，可能測試資料也不是很大，
所以主動用排序帶來的負面效益較低的原因)

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N), O(N)
每個陣列均會掃過一次，且會產生一個新的陣列。)

「這題在產生新的陣列的時候跟合併排序(Merge Sort)其實很像，
可以概略描述Merge Sort的作法嗎？」
(可以XD 這個我們之後會專門寫一題講解)
(如果不想等的話，可以先查詢Merge Sort，應該有蠻多資料的，
但簡言之，就是每次將陣列拆兩半，
分別各自排序過後(mergesort)，再依序合併起來(merge)。)

相似及延伸：
1. 0021. Merge Two Sorted Lists (Easy)
2. 0148. Sort List (Medium)

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~