LeetCode 解題練習：Squares of a Sorted Array

 若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/squares-of-a-sorted-array/

中文描述

給定一個由小排到大的整數陣列 nums ，算出每個數字的平方，並由小排到大排序。


限制條件：

• 1 <= nums.length <= 10000
• -10000 <= nums[i] <= 10000

範例一：

輸入 nums = [-4, -1, 0, 2, 3]

輸出 [0, 1, 4, 9, 16]

平方後 [16, 1, 0, 4, 9]，排序後 [0, 1, 4, 9, 16]

解法一：

算出每個數字平方後，再做排序。

Python Code

class Solution:

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

        for i in range(len(nums)):

            nums[i] = nums[i] * nums[i]

       

        return sorted(nums)

解法二：

用兩個指標 left 與 right 分別指到陣列的開頭索引 0 與結束索引 len(nums) - 1。

maxIdx 為目前找到的最大值之索引位置。可參考底下動畫圖片

Python Code

class Solution:

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

        res = [0] * len(nums) # 存放結果的陣列

        right = len(nums) - 1 # 陣列結束索引

        left = 0 # 陣列開頭索引

        maxIdx = right # 從最大值開始找起

   

        while maxIdx >= 0:

            if abs(nums[left]) > abs(nums[right]):

                res[maxIdx] = nums[left] ** 2 # 陣列最左邊較大

                left += 1 # 左邊指標往右移

            else:

                res[maxIdx] = nums[right] ** 2 # 陣列最右邊較大

                right -= 1 # 右邊指標往左移

           

            maxIdx -= 1 # 下一個次大值索引

        return res