Leetcode 977 Squares of a Sorted Array

发表于 |

给定一个数组A（单调递增），将A中的每个数进行平方后再进行排序，返回最后排序的结果。

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. 1 <= A.length <= 10000
  2. -10000 <= A[i] <= 10000
  3. A is sorted in non-decreasing order.

题意分析：
如果说直接先平方再用库函数进行排序的话，那数组A本身有序这个条件就没有用处了。
既然题目给出这个条件，那么想必是想让我们使用比O(nlogn)更优的方法来解题。

由于数组本身有序，我们想到用双指针来判断，例如对于数组 [-7,-3,2,3,11]，平方后最大的数一定会在负数中的最小值(-7)和正数中的最大值(11)中产生，然后第二大的数会在负数中的最小值(-7)和正数中的第二大值(3)中产生，依次类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def sortedSquares(self, A):
        res = []
        i, j = 0, len(A)-1
        while i <= j:
            if A[i]**2 > A[j]**2:
                res.append(A[i]**2)
                i += 1
            else:
                res.append(A[j]**2)
                j -= 1
        return res[::-1]

# 132 / 132 test cases passed.
# difficulty: easy
# Runtime: 192 ms