思路①:先平方,后快排,输出(基准元素,左小右大)
时间复杂度: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;
}