刷题第2天：LeetCode977--有序数组的平方--双指针法

本文主要是介绍刷题第2天：LeetCode977--有序数组的平方--双指针法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LeetCode977题：

给你一个按 非递减顺序 排序的整数数组 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 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序

思路分析：

1.最简单的方法是先平方，然后使用快速排序，这是暴力解法，计算复杂度略高；

2.给出的数组是有序的，只不过包含负数，负数平方之后可能会成为最大的数，所以需要进行判别；

3.数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间，这就可以考虑双指针法了，i指向起始位置，j指向终止位置。再定义一个新数组result，和给的原始数组一样的大小，让k指向result数组终止位置。

# 双指针法
class Solution:def sortedSquares(self, nums:List[int]) -> List[int]:left, right, i = 0, len(nums)-1, len(nums)-1result = [float('inf)] * len(nums) # 需要提前定义列表，存放结果while left <= right:if nums[left] ** 2 < nums[right] ** 2:  # 左右边界进行对比，找出最大值result[i] = nums[right] ** 2right -= 1 # 右指针往左移动else:result[i] = nums[left]**2left += 1  #左指针向右移动i -= 1 # 存放结果的指针需要向小的方向平移一位return result

总结：本题的关键是给定的数组是有序的，且可以包含负数，则平方后的最大值会出现的数组的两端，采用双指针法比较得出平方后的最大值，并将最大值存入到结果数组中。注意与第1天移除元素中采用的快慢指针相区别。快慢指针的起始下标都是0，而本题则是一个是左指针，一个是右指针，起始点不同。

这篇关于刷题第2天：LeetCode977--有序数组的平方--双指针法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---