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?

題目翻譯

今天已經有一個升序排列的陣列 nums，然後需要將其中的元素都變成平方值之後再依照平方後的大小排列。其中可以的話，想辦法達到時間複雜度 O(n)

解法解析

今天在不考慮時間複雜度的條件下，我們可以很單純的使用一些內建的函數來快速的達到這個需求。但是如果要達到時間複雜度的限制的話，就會需要使用到 Two Pointers 來做解答。因為這個陣列本身就已經排序過了，考量有負值的情況下，平方後大小的排序其實就會是從兩側往內部縮小。所以使用 Two pointers 剛好符合使用情境。

解法範例

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
    }
}