LeetCode Solution, Easy, 977. Squares of a Sorted Array
排序陣列的平方
Published
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**4numsis 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
}
}