# 977. Squares of a Sorted Array

## 題目敘述

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?

## 解法解析

### 解法範例

#### Go

##### Built-In
``````func sortedSquares(nums []int) []int {
for i, val := range nums {
nums[i] = val * val
}
sort.Ints(nums)
return nums
}
``````
##### Two Pointers
``````func sortedSquares(nums []int) []int {
var n, lastIndex, left, right int = len(nums), len(nums) - 1, 0, len(nums) - 1
result := make([]int, n)

for left <= right {
var leftSquare, rightSquare int = nums[left] * nums[left], nums[right] * nums[right]

if leftSquare < rightSquare {
result[lastIndex] = rightSquare
right--
} else {
result[lastIndex] = leftSquare
left++
}
lastIndex--
}
return result
}
``````

#### JavaScript

##### Built-In
``````/**
* @param {number[]} nums
* @return {number[]}
*/
var sortedSquares = function (nums) {
return nums.map((num) => num * num).sort((a, b) => a - b);
};
``````
##### Two Pointers
``````/**
* @param {number[]} nums
* @return {number[]}
*/
var sortedSquares = function (nums) {
const n = nums.length,
result = new Array(n).fill(0);
let lastIndex = n - 1;

for (let left = 0, right = n - 1; left <= right; ) {
const leftSquare = nums[left] ** 2;
const rightSquare = nums[right] ** 2;
if (leftSquare < rightSquare) {
result[lastIndex--] = rightSquare;
right--;
} else {
result[lastIndex--] = leftSquare;
left++;
}
}
return result;
};
``````

#### Kotlin

##### Built-In
``````class Solution {
fun sortedSquares(nums: IntArray): IntArray {
return nums.map { it * it }.sorted().toIntArray()
}
}
``````
##### Two Pointers
``````class Solution {
fun sortedSquares(nums: IntArray): IntArray {
val n = nums.size
val result = IntArray(n)
var left = 0
var right = n - 1
var idx = n - 1

while (left <= right) {
val leftSquare = nums[left] * nums[left]
val rightSquare = nums[right] * nums[right]

if (leftSquare <= rightSquare) {
result[idx] = rightSquare
right--
} else {
result[idx] = leftSquare
left++
}
idx--
}

return result
}
}
``````

#### PHP

##### Built-In
``````class Solution
{

/**
* @param Integer[] \$nums
* @return Integer[]
*/
function sortedSquares(\$nums)
{
\$ans = array_map(function (\$num) {
return \$num * \$num;
}, \$nums);
sort(\$ans);
return \$ans;
}
}
``````
##### Two Pointers
``````class Solution
{

/**
* @param Integer[] \$nums
* @return Integer[]
*/
function sortedSquares(\$nums)
{
\$n = count(\$nums);
\$result = array_fill(0, \$n, 0);
\$left = 0;
\$right = \$n - 1;
\$lastIndex = \$n - 1;
while (\$left <= \$right) {
\$leftSquare = \$nums[\$left] ** 2;
\$rightSquare = \$nums[\$right] ** 2;
if (\$leftSquare < \$rightSquare) {
\$result[\$lastIndex] = \$rightSquare;
\$right--;
} else {
\$result[\$lastIndex] = \$leftSquare;
\$left++;
}
\$lastIndex--;
}
return \$result;
}
}
``````

#### Python

##### Built-In
``````class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
return sorted(num * num for num in nums)
``````
##### Two Pointers
``````class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
n = len(nums)
result = [0] * n
left = 0
right = n - 1
for i in range(n - 1, -1, -1):
if abs(nums[left]) < abs(nums[right]):
square = nums[right]
right -= 1
else:
square = nums[left]
left += 1
result[i] = square ** 2
return result
``````

#### Rust

##### Built-In
``````impl Solution {
pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {
let mut res: Vec<i32> = nums.iter().map(|&x| x * x).collect();
res.sort();
res
}
}
``````
##### Two Pointers
``````impl Solution {
pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {
let mut result = vec![0; nums.len()];
let mut left = 0;
let mut right = nums.len() as i32 - 1;
for i in (0..nums.len()).rev() {
let mut square = 0;
let left_square = nums[left as usize] * nums[left as usize];
let right_square = nums[right as usize] * nums[right as usize];
if left_square > right_square {
result[i] = left_square;
left += 1;
} else {
result[i] = right_square;
right -= 1;
}
}

result
}
}
``````

#### Swift

##### Built-In
``````class Solution {
func sortedSquares(_ nums: [Int]) -> [Int] {
return nums.map { \$0 * \$0 }.sorted()
}
}
``````
##### Two Pointers
``````class Solution {
func sortedSquares(_ nums: [Int]) -> [Int] {
let n = nums.count
var left = 0
var right = n - 1
var result = Array(repeating: 0, count: n)

for i in (0..<n).reversed() {
var square = 0
if abs(nums[left]) > abs(nums[right]) {
square = nums[left]
left += 1
} else {
square = nums[right]
right -= 1
}
result[i] = square * square
}

return result
}
}
``````