有序数组的平方
时间: 2024-02-05 13:11:03 浏览: 23
对于一个有序数组,可以使用双指针的方法求出平方后的有序数组。
具体做法如下:
1. 定义两个指针 left 和 right,分别指向数组的第一个元素和最后一个元素。
2. 定义一个新的数组 result,用来存放平方后的结果。
3. 定义一个变量 index,表示存放结果的索引,初始值为数组的最后一个元素的索引。
4. 比较 left 和 right 指向的元素的绝对值大小,将较大的平方值存入 result 数组中,并将指向该元素的指针向中间移动一位。
5. 重复第4步,直到 left 和 right 指针重合。
6. 最后,将 result 数组反转并返回即可。
以下是 Python 代码实现:
```python
def sortedSquares(nums):
n = len(nums)
left, right = 0, n - 1
result = [0] * n
index = n - 1
while left <= right:
if abs(nums[left]) > abs(nums[right]):
result[index] = nums[left] ** 2
left += 1
else:
result[index] = nums[right] ** 2
right -= 1
index -= 1
return result[::-1]
```
例如,对于有序数组 [-4, -2, 0, 2, 4],平方后得到的有序数组为 [0, 4, 16, 16, 16]。