977. 有序数组的平方

给定一个按非递减顺序排序的整数数组A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例1:

输入：[-4, -1, 0, 3, 10]
输出：[0, 1, 9, 16, 100]

示例2:

输入：[-7, -3, 2, 3, 11]
输出：[4, 9, 9, 49, 121]

提示：

1. 1<= A.length <= 1000

2. -10000 <= A[i] <= 10000

3. A已按非递减顺序排序。

思路与代码

方法一： 直接排序

思路：

最简单的方法就是将数组A中的数平方后直接排序。

code:

class Solution:
	def sortedSquares(self, A: List[iht]) -> List[int]:
		return sorted(num * num for num in A)

复杂度分析：

• 时间复杂度：$O(nlogn)$，其中$n$是数组$A$的长度。
• 空间复杂度：$O(logn)$， 除了存储答案的数组以外，我们需要$O(logn)$的栈空间进行排序。

方法二：双指针

思路：

方法一没有利用【数组A已经按照升序排序】这个条件。显然，如果数组A中的所有数都是非负数，那么将每个数平方后，数组仍然保持升序；如果数组A中的所有数都是负数，那么将每个数平方后，数组会保持降序。

找到数组A中负数与非负数的分界线，利用类似【归并排序】的方法。具体而言，我们设neg为数组A中负数与非负数的分界线。A[0]与A[neg]均为负数，而A[neg+1]到A[n-1]均为非负数。当我们将数组A中的数平方后，那么A[0]到A[neg]单调递减，A[neg]到A[n-1]单调递增。

由于我们已经得到了两个已经有序的子数组，因此可以使用归并的方法进行排序。具体，使用两个指针分别指向位置neg和neg+1，每次比较两个指针对应的数，选择较小的那个放入答案并移动指针。当某一指针指向边界时，将另一指针还未遍历到的数依次放入答案。

code:

class Solution:
    def sortedSquares(self, A):
        # 方法一
        n = len(A)
        if n == 1:
            return [A[0] * A[0]]
        ans = []
        negative = 0
        for num in range(n):
            if A[num] < 0:
                negative = num
            else:
                break
        i, j = negative, negative + 1
        while i >= 0 or j < n:
            print(i, j)
            if i < 0:
                ans.append(A[j] * A[j])
                print('左边已经结束', A[j] * A[j])
                j += 1
            elif j == n:
                ans.append(A[i] * A[i])
                print("右边已经结束", A[i] * A[i])
                i -= 1
            elif A[i] * A[i] < A[j] * A[j]:
                ans.append(A[i] * A[i])
                print('i<j', A[i] * A[i])
                i -= 1
            else:
                ans.append(A[j] * A[j])
                print('i>j', A[j] * A[j])
                j += 1
        return ans

复杂度分析：

• 时间复杂度：$O(n)$，其中$n$是数组$A$的长度。
• 空间复杂度：$O(1)$。

方法三：双指针

思路：

使用两个指针分别指向位置$0$和$n-1$，每次比较两个指针所对应的数的平方，选择较大的结果逆序放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况。当两个指针重合的时候，算法结束。

code:

class Solution:
    def sortedSquares(self, A):
        n = len(A)
        ans = [0] * n
        i, j, pos = 0, n-1, n-1
        while i <= j:
            if A[i] * A[i] > A[j] * A[j]:
                ans[pos] = A[i] * A[i]
                i += 1
            else:
                ans[pos] = A[j] * A[j]
                j -= 1
            pos -= 1
        return ans

复杂度分析：

• 时间复杂度：$O(n)$，其中$n$是数组$A$的长度。
• 空间复杂度：$O(1)$。