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 步,直到各个部分只有一个数,则排序结束。
代码 #
- 双指针:
|
|
- 排序算法
|
|