【LeetCode】977. Squares of a Sorted Array 解答・解説【Python】

問題
1. 原文
2. 内容
方針
1. 前提
2. 実装のイメージ
解答
補足・参考・感想

問題

原文

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].

1
2
3
4

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]

1
2

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Constraints:

1 <= nums.length <= 10⁴

-10⁴ <= nums[i] <= 10⁴

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 pointerを使う

実装のイメージ

解答

解答1：

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        squared_list = []
        for i in nums:
            squared_list.append(i**2)
        
        return sorted(squared_list)か

class Solution:

def sortedSquares(self, nums: List[int]) -> List[int]:

squared_list = []

for i in nums:

squared_list.append(i**2)

return sorted(squared_list)か

各要素を二乗してソートした。何も考えずに解くとこうなった。

たぶん、これだけで終わっちゃいけない。

解答2

#配列numsは昇順に並べられている
#two pointer で両端を狭めていき、各要素を1順走査する

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        #lは左側、rは右側のポインタ
        l, r = 0, len(nums) - 1 
        res = [] 

        #lがr以下の限り繰り返す
        while l <= r:
            #左側の要素の絶対値が右側の要素の絶対値よりも大きい場合    
            if abs(nums[l]) > abs(nums[r]):
				#resに左側の要素の2乗を追加
                res.append(nums[l]**2)
                #lを一つ右に進める
                l += 1 
            #左側の要素の絶対値が右側の要素の絶対値以下の場合    
            else:
                #resに右側の要素の二乗を追加
                res.append(nums[r]**2)
                #右側のポインタを一つ左に進める
                r -= 1 
        #resを逆順にして返す
        print(res)
        return res[::-1]

#配列numsは昇順に並べられている

#two pointer で両端を狭めていき、各要素を1順走査する

class Solution:

def sortedSquares(self, nums: List[int]) -> List[int]:

#lは左側、rは右側のポインタ

l, r = 0, len(nums) - 1

res = []

#lがr以下の限り繰り返す

while l <= r:

#左側の要素の絶対値が右側の要素の絶対値よりも大きい場合

if abs(nums[l]) > abs(nums[r]):

#resに左側の要素の2乗を追加

res.append(nums[l]**2)

#lを一つ右に進める

l += 1

#左側の要素の絶対値が右側の要素の絶対値以下の場合

else:

#resに右側の要素の二乗を追加

res.append(nums[r]**2)

#右側のポインタを一つ左に進める

r -= 1

#resを逆順にして返す

print(res)

return res[::-1]

two pointerを使うと時間計算量O(n)で解けるらしい。

両端に2つポインタを置き、絶対値の大きい方を別の配列に格納していく。

絶対値の大きい順に格納していくので、最後に逆順にして返せば良い。

また、numsは昇順で用意してくれている。

[-3,-,2,-1,0,1,2,3]

両端に近づくほど絶対値は大きくなり、真ん中に近づくほど絶対値は小さくなる。

だから両端から絶対値の大きい方を比較し、1つずつ内側に向かって操作することで二乗後の配列は降順で作ることができる。

配列を新しく用意するので、空間計算量はO(n)で合っているのかな？

解答3：Rust

impl Solution {
    pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {
        let mut result = vec![0; nums.len()];
        if !nums.is_empty() {
            let mut left = nums.iter().map(|x| x.pow(2)).peekable();
            let mut right = nums.iter().rev().map(|x| x.pow(2)).peekable();
            for i in (0..nums.len()).rev() {
                result[i] = if left.peek().unwrap() > right.peek().unwrap() {
                    left.next().unwrap()
                } else {
                    right.next().unwrap()
                }
            }
        }
        result
    }
}

impl Solution {

pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {

let mut result = vec![0; nums.len()];

if !nums.is_empty() {

let mut left = nums.iter().map(|x| x.pow(2)).peekable();

let mut right = nums.iter().rev().map(|x| x.pow(2)).peekable();

for i in (0..nums.len()).rev() {

result[i] = if left.peek().unwrap() > right.peek().unwrap() {

left.next().unwrap()

} else {

right.next().unwrap()

}

result

}

丸パクリだけど写経させていただいた。Python以外も書けるようになりたい。

補足・参考・感想

■補足

square：二乗

non-decreasing order：非降順

■参考

■感想

two pointerを使える問題もそろそろ自力で解きたい

両端から狭めるパターン、両端に向けて広がるパターン、for文の中で1つ進むポインタと2つ進むポインタがあるパターンなど整理したい。

前：15. 3Sum

次：283. Move Zeroes

LeetCode 解答・解説記事一覧