LeetCode977有序数组的平方
目录
LeetCode977有序数组的平方
思路①：先平方，后快排，输出（基准元素，左小右大）
时间复杂度：O（nlogn）
思路②：双指针左右开弓，首先原数组已经是按照非递减顺序排序，那么最大值只有可能出现在最右边或者最左边，那么我们可以创建一个与原数组等长的空数组，双指针，i指向原数组的最左边，j指向最右边，每次循环都判断是左边大还是右边大，将大的值放入空数组中（空数组的指针k从末尾往前跳，最末尾是最大的值）
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
int *output=(int*)malloc(sizeof(int) * numsSize);
int k=numsSize-1;
int i=0,j=numsSize-1;
while(i<=j)
{
if(nums[i]*nums[i]<nums[j]*nums[j])
{
output[k--]=nums[j]*nums[j];//谁大放谁
j--;
}
else
{
output[k--]=nums[i]*nums[i];
i++;
}
}
*returnSize = numsSize;//设置返回数组的大小
return output;
}