Leetcode-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 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非递减顺序排序。

方法

方法1：排序 sorted()或list.sort()

创建一个新的数组，它每个元素是给定数组对应位置元素的平方，然后排序这个数组。

class Solution(object):
    def sortedSquares(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        return sorted(x*x for x in A)

复杂度分析

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

  class Solution(object):
      def sortedSquares(self, A):
          """
          :type A: List[int]
          :rtype: List[int]
          """
          A=[x**2 for x in A]
          A.sort()
          return A

方法2：双指针

思路

因为数组 A 已经排好序了， 所以可以说数组中的负数已经按照平方值降序排好了，数组中的非负数已经按照平方值升序排好了。

举一个例子，若给定数组为 [-3, -2, -1, 4, 5, 6]，数组中负数部分 [-3, -2, -1] 的平方为 [9, 4, 1]，数组中非负部分 [4, 5, 6] 的平方为 [16, 25, 36]。我们的策略就是从前向后遍历数组中的非负数部分，并且反向遍历数组中的负数部分。

算法

我们可以使用两个指针分别读取数组的非负部分与负数部分 —— 指针 i 反向读取负数部分，指针 j 正向读取非负数部分。

那么，现在我们就在使用两个指针分别读取两个递增的数组了（按元素的平方排序）。接下来，我们可以使用双指针的技巧合并这两个数组

class Solution(object):
    def sortedSquares(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        N=len(A)
        j=0
        while j<N and A[j]<0:
            j+=1
        i=j-1

        ans=[]
        while i>=0 and j<N:
            if A[i]**2<A[j]**2:
                ans.append(A[i]**2)
                i-=1
            else:
                ans.append(A[j]**2)
                j+=1
        while i>=0:
            ans.append(A[i]**2)
            i-=1
        while j<N:
            ans.append(A[j]**2)
            j+=1
        return ans

复杂度分析

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

  参考资料

• Python 内置函数list.sort()& sorted()对比及时间和空间复杂度分析
• Python sort 的实现 - Timsort 算法
• leetcode 977 solution