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 <= nums.length <= 104-104 <= nums[i] <= 104-
nums已按 非递减顺序 排序
进阶：
- 请你设计时间复杂度为
O(n)的算法解决本问题
思路：
这道题拿到手，第一反应肯定是，可以使用最简单的方法，将数组中的所有元素进行平方处理，构建新数组，再进行排序。
然而，这肯定不是最优解，这道题同样也可以尝试使用双指针法进行求解。
暴力求解：
将每个数平方后，再进行排序，这里不光要用到一个for循环，还需要用到sort函数，所以时间复杂度为O(n + nlogn)，可以看作是O(nlogn)
注：运用sort函数需要加上algorithm头文件
class Solution {
public:
//暴力平方
vector<int> sortedSquares(vector<int>& A) {
for (int i = 0; i < A.size(); i++) {
A[i] *= A[i]; //将数组中每个数平方
}
sort(A.begin(), A.end()); // 快速排序
return A;
}
};
双指针法：
对于数组，双指针法是一种十分常用的方法，而这道题我们也可以尝试使用双指针法进行求解。
这里有个十分关键的点，就是：原本的数组本身就是有序的，是一个非递减的数组，那么即使数组中元素有正有负，绝对值最大的元素肯定是在数组的两端的，即数组平方的最大值是在数组的两端的。
所以我们可以使用两个双指针i,j一个指向起始位置，一个指向数组的末尾。
定义一个新的数组result用于储存新的有序平方后的元素。
这里有两条重要的判断语句：
- 如果
A[i] * A[i] < A[j] * A[j]那么result[k--] = A[j] * A[j];。 - 如果
A[i] * A[i] >= A[j] * A[j]那么result[k--] = A[i] * A[i];。
class Solution {
public:
//双指针
vector<int> sortedSquares(vector<int>& A) {
int k = A.size() - 1; //指向新数组的末尾，从后往前赋值
vector<int> result(A.size(), 0);
for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要i <= j，因为最后要处理两个元素
if (A[i] * A[i] < A[j] * A[j]) { //判断条件1：尾部元素更大
result[k--] = A[j] * A[j];
j--;
}
else {
result[k--] = A[i] * A[i]; //判断条件2：头部元素更大
i++;
}
}
return result;
}
};
时间复杂度为O(n)。
后续也会坚持更新我的LeetCode刷题笔记，欢迎大家关注我，一起学习。
如果这篇文章对你有帮助，或者你喜欢这篇题解，可以给我点个赞哦。
CSDN同步更新，欢迎关注我的博客：一粒蛋TT的博客_CSDN博客-LeetCode学习笔记,HTML+CSS+JS,数据结构领域博主
往期回顾：
LeetCode844.比较含退格的字符串
LeetCode283.移动零
LeetCode27.移除元素
LeetCode26.删除有序数组中的重复项
