难度简单608
给你一个按 非递减顺序 排序的整数数组 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] <= 104nums已按 非递减顺序 排序
思路一：暴力
直接将数组内的值平方后调用库函数排序即可，库中的排序是快速排序。
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;
}
};这个时间复杂度是 O(n + nlogn)， 可以说是O(nlogn)的时间复杂度，但为了和下面双指针法算法时间复杂度有鲜明对比，我记为 O(n + nlog n)。
思路二：从中间开始的第一个非负数排序
我们可以先对特殊情况处理一下：
- 若数组都为正：即 nums[0] >= 0，则直接平方然后返回原数组即可
- 若数组都为负：即 num[nums.size() - 1] < 0，则将其平方后逆置返回即可
剩下的情况就是既有正，又有负的情况了！
方法：
- 首先找到第一个出现的非负数字，然后用 mid 标记其下标
- 然后设 left 为 mid 的左边的下标
- 然后将 nums[mid] 与 nums[left] 处的元素开始比较，谁小就将谁放到新数组 tmp 中
- 直到两个小标都出界为止
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> v;
int mid = nums.size() - 1; // 存放的就是第一个大于0数字
// 循环一遍看看是否存在第一个大于0的数字
for(int i = 0; i < nums.size() - 1; ++i)
{
if(nums[i] > 0 && nums[i] <= nums[i + 1])
{
mid = i;
break;
}
}
// 开始比较谁小，从中间往两侧延伸
// 规定left向左走，mid向右走
int left = mid - 1;
while(left >= 0 && mid < nums.size())
{
if(abs(nums[left]) <= abs(nums[mid]))
{
tmp.push_back(nums[left]*nums[left]);
left--;
}
else
{
tmp.push_back(nums[mid]*nums[mid]);
mid++;
}
}
while(left >= 0)
{
tmp.push_back(nums[left]*nums[left]);
left--;
}
while(mid < nums.size())
{
tmp.push_back(nums[mid]*nums[mid]);
mid++;
}
return tmp;
}
};可以看出时间复杂度其实也是 O(n)，但是好像代码有点长，不如看一看下面这种
思路三：从首尾往中间排序
数组其实是有序的， 只不过负数平方之后可能成为最大数了。
那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
此时可以考虑双指针法了，i指向起始位置，j指向终止位置。
定义一个新数组result，和nums数组一样的大小，让k指向result数组终止位置。
如果nums[i] * nums[i] < nums[j] * nums[j] 那么result[k--] = nums[j] * nums[j]; 。
如果nums[i] * nums[i] >= nums[j] * nums[j] 那么result[k--] = nums[i] * nums[i]; 。
和思路二不同的是，思路三是找谁大，然后将其放到tmp的尾部，而思路二是找小的那个放到tmp的头部，从这里来看，思路三会更简便一点！
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> v(nums.size());
int vi = v.size() - 1;
int left = 0;
int right = nums.size() - 1;
while(left <= right)
{
if(abs(nums[left]) <= abs(nums[right]))
{
v[vi--] = nums[right]*nums[right];
right--;
}
else
{
v[vi--] = nums[left]*nums[left];
left++;
}
}
return v;
}
};此时的时间复杂度为O(n)，相对于暴力排序的解法O(n + nlog n)还是提升不少的。
