# leetcode - Squares of a Sorted Array
Date: 2021-06-11


#### **问题**

Given an integer array `nums` sorted in **non-decreasing** order, return _an array of **the squares of each number** sorted in non-decreasing order_.

**Example 1:**

**Input:**

```
 nums = [-4,-1,0,3,10]

```

**Output:**

```
 [0,1,9,16,100]

```

**Explanation:**

```
After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

```

**Example 2:**

**Input:**

```
 nums = [-7,-3,2,3,11]

```

**Output:**

```
 [4,9,9,49,121]

```

**Constraints:**

- `1 <= nums.length <= 10`4
- `-10`4 `<= nums[i] <= 10`4
- `nums` is sorted in **non-decreasing** order.

**Follow up:** Squaring each element and sorting the new array is very trivial, could you find an `O(n)` solution using a different approach?

#### **解答:**

##### **平方后排序**

新申请一个数组存放平方数，之后进行排序即可

时间复杂度 O(nlogn) 依赖与排序算法，如堆排序，并归排序

空间复杂度 O(n) 平方数组

```
# time complexity O(nlogn)  space complexity O(n)
def sortedSquaredArray(array):
    # Write your code here.
    sortedSquares = []
    for value in array:
        squareValue = value * value
        sortedSquares.append(squareValue)
    sortedSquares.sort()
    return sortedSquares
```

##### **双指针**

由于原有数组的排序的，平方和最大情况，可能会发生在数组两端， 通过两个指针从数组两端开始，比较将平方和大的放到新数组中。

时间复杂度 O(n) 依赖与排序算法，如堆排序，并归排序

空间复杂度 O(n) 平方数组

```
def sortedSquaredArray(array):
    # Write your code here.
    sortedSquares = [0  for _ in array]
    smallIdx = 0 
    largeIdx = len(array) - 1
    
    for idx in reversed(range(len(array))):
        smallerValue = array[smallIdx]
        largerValue = array[largeIdx]
        
        if abs(largerValue) > abs(smallerValue):
            sortedSquares[idx]  = largerValue * largerValue
            largeIdx = largeIdx - 1
        else:
            sortedSquares[idx] = smallerValue * smallerValue
            smallIdx = smallIdx + 1
        
    return sortedSquares

```

 

#### **参考及引用**

Photo by **[Erik Karits](https://www.pexels.com/@erik-karits-2093459?utm_content=attributionCopyText&utm_medium=referral&utm_source=pexels)** from **[Pexels](https://www.pexels.com/photo/brown-owl-perched-on-brown-tree-branch-3782463/?utm_content=attributionCopyText&utm_medium=referral&utm_source=pexels)**