0977. 有序数组的平方
大约 2 分钟
0977. 有序数组的平方
- 标签:数组、双指针、排序
- 难度:简单
题目大意
描述:给你一个按「非递减顺序」排序的整数数组 nums
。
要求:返回「每个数字的平方」组成的新数组,要求也按「非递减顺序」排序。
解题思路
思路 1:双指针
原数组是按「非递减顺序」排序的,可能会存在负数元素。但是无论是否存在负数,数字的平方最大值一定在原数组的两端。题目要求返回的新数组也要按照「非递减顺序」排序。那么,我们可以利用双指针,从两端向中间移动,然后不断将数的平方最大值填入数组。具体做法如下:
使用两个指针
left
、right
。left
指向数组第一个元素位置,right
指向数组最后一个元素位置。再定义index = len(nums) - 1
作为答案数组填入顺序的索引值。res
作为答案数组。比较
nums[left]
与nums[right]
的绝对值大小。大的就是平方最大的的那个数。如果
abs(nums[right])
更大,则将其填入答案数组对应位置,并令right -= 1
。如果
abs(nums[left])
更大,则将其填入答案数组对应位置,并令left += 1
。令
index -= 1
。
直到
left == right
,最后将nums[left]
填入答案数组对应位置。
返回答案数组 res
。
思路 2:排序算法
可以通过各种排序算法来对平方后的数组进行排序。以快速排序为例,具体步骤如下:
- 遍历数组,将数组中各个元素变为平方项。
- 从数组中找到一个基准数。
- 然后将数组中比基准数大的元素移动到基准数右侧,比他小的元素移动到基准数左侧,从而把数组拆分为左右两个部分。
- 再对左右两个部分分别重复第 2、3 步,直到各个部分只有一个数,则排序结束。
代码
- 双指针:
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
size = len(nums)
left, right = 0, size - 1
index = size - 1
res = [0 for _ in range(size)]
while left < right:
if abs(nums[left]) < abs(nums[right]):
res[index] = nums[right] * nums[right]
right -= 1
else:
res[index] = nums[left] * nums[left]
left += 1
index -= 1
res[index] = nums[left] * nums[left]
return res
- 排序算法
import random
class Solution:
def randomPartition(self, arr: [int], low: int, high: int):
i = random.randint(low, high)
arr[i], arr[high] = arr[high], arr[i]
return self.partition(arr, low, high)
def partition(self, arr: [int], low: int, high: int):
i = low - 1
pivot = arr[high]
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quickSort(self, arr, low, high):
if low < high:
pi = self.randomPartition(arr, low, high)
self.quickSort(arr, low, pi - 1)
self.quickSort(arr, pi + 1, high)
return arr
def sortedSquares(self, nums: List[int]) -> List[int]:
for i in range(len(nums)):
nums[i] = nums[i] * nums[i]
return self.quickSort(nums, 0, len(nums) - 1)