更多精彩內(nèi)容，請關(guān)注【力扣簡單題】。

題目

難度：★☆☆☆☆
類型：數(shù)組

給定一個(gè)按非遞減順序排序的整數(shù)數(shù)組 A，返回每個(gè)數(shù)字的平方組成的新數(shù)組，要求也按非遞減順序排序。

提示
1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非遞減順序排序。

示例

示例 1
輸入：[-4,-1,0,3,10]
輸出：[0,1,9,16,100]

示例 2
輸入：[-7,-3,2,3,11]
輸出：[4,9,9,49,121]

解答

方案1：暴力求解

我們對輸入數(shù)組中每個(gè)元素進(jìn)行平方，然后對結(jié)果進(jìn)行數(shù)組進(jìn)行排序即可。

class Solution:
    def sortedSquares(self, A):
        return sorted(map(lambda x: x*x, A))

方案2：雙指針

（參考官方解答）

我們可以使用兩個(gè)指針分別讀取數(shù)組的非負(fù)部分與負(fù)數(shù)部分 —— 指針 i 反向讀取負(fù)數(shù)部分，指針 j 正向讀取非負(fù)數(shù)部分。

那么，現(xiàn)在我們就在使用兩個(gè)指針分別讀取兩個(gè)遞增的數(shù)組了（按元素的平方排序）。接下來，我們可以使用雙指針的技巧合并這兩個(gè)數(shù)組。

class Solution(object):
    def sortedSquares(self, A):
        N = len(A)

        # 首先，我們找到負(fù)數(shù)和非負(fù)數(shù)的分界點(diǎn)j，代表最大的一個(gè)負(fù)數(shù)
        p = 0                           # 正數(shù)指針
        while p < N and A[p] < 0:
            p += 1

        n = p - 1

        ans = []
        while 0 <= n and p < N:
            if A[n]**2 < A[p]**2:       # 正數(shù)的平方比負(fù)數(shù)大
                ans.append(A[n]**2)     # 添加較小的平方數(shù)
                n -= 1
            else:
                ans.append(A[p]**2)
                p += 1

        # 如果還有剩余負(fù)數(shù)，繼續(xù)添加
        while n >= 0:
            ans.append(A[n]**2)
            n -= 1

        # 如果還有剩余正數(shù)，繼續(xù)添加
        while p < N:
            ans.append(A[p]**2)
            p += 1

        return ans

如有疑問或建議，歡迎評論區(qū)留言~