題目

977. 有序數組的平方

給你一個按 非遞減順序 排序的整數數組 nums，返回 每個數字的平方 組成的新數組，要求也按 非遞減順序 排序。

示例 1：

輸入：nums = [-4,-1,0,3,10]
輸出：[0,1,9,16,100]
解釋：平方后，數組變為 [16,1,0,9,100]
排序后，數組變為 [0,1,9,16,100]

示例 2：

輸入：nums = [-7,-3,2,3,11]
輸出：[4,9,9,49,121]

代碼

1. 使用sorted

直接平方，使用sorted

class Solution(object):def sortedSquares(self, nums):""":type nums: List[int]:rtype: List[int]"""# 數組元素只能覆蓋for i in range(len(nums)):nums[i] = nums[i] * nums[i]return sorted(nums)

2. 雙指針

思路： 非遞減順序：才能使用雙指針
判斷左右兩邊的平方，將大的平方放在右邊，右邊的指針-1

class Solution(object):def sortedSquares(self, nums):""":type nums: List[int]:rtype: List[int]"""# 非遞減順序：才能使用雙指針left = 0right = len(nums) - 1result = [0] * len(nums)pos = len(nums) - 1while left <= right:if nums[left] * nums[left] < nums[right] * nums[right]:result[pos] = nums[right] * nums[right]right -= 1else:result[pos] = nums[left] * nums[left]left += 1pos -= 1return result