0977. Squares of a Sorted Array - chasel2361/leetcode GitHub Wiki

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:
Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 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.

這題給定一個排序後的陣列，要求回傳由小至大排序後、其陣列值之平方數，一開始題目沒看清楚，沒發現給定的陣列已經排序了，想說又要排序又要取平方值有點麻煩想了一下，後來才發現自己眼殘，題目比想像中的簡單。

第一個想法是，先把 A 的所有值代換成其平方數，再使用 list.sort() 函數排序，這樣雖然有點偷吃步，沒有自己排序，但可以解決給定陣列沒有先排序的狀況。

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        if not A: return []
        for i, a in enumerate(A):
            A[i] = a*a
        A.sort()
        return A

這樣寫的時間複雜度應該是 O(N+NlogN) = O(NlogN)，空間複雜度是由 sort 函式帶來的 O(N)

---

那如果考慮到給定陣列已經排序過了的話，就可以使用 two-pointer的方法來解，先把陣列值代換成其絕對值，在從外到內對左右兩個 pointer 比大小，大的就取平方值丟進 res 裡

[1] i 作為 res 的 index，會從 0 到 len(A) - 1

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        len_A = len(A)
        i = len_A - 1
        r, l = i, 0
        res = [0] * len_A
        
        for i in range(len_A):
            A[i] = abs(A[i])
            
        while i >= 0:  # [1]
            Al, Ar = A[l], A[r]
            if Al > Ar:
                res[i] = Al ** 2
                l += 1
            else:
                res[i] = Ar ** 2
                r -= 1
            i -= 1
        return res

這個寫法的時間複雜度為 O(N+N) = O(N)，空間複雜度也是 O(N)