image-20241104082610943

可以直接平方快排,时间复杂度就是n+n*logn;

这里用上前后指针可以很好地解决;

原数组是递增的,因此最大的要么在最左边,要么在最右边

我们只需要比较两者大小,塞进新数组(从后往前塞),然后原数组的左指针后移或者右指针前移

当left>right时停止(相等的时候也要把那个数搞进新数组)

最终代码:

1
2
3
4
5
6
7
8
9
10
11
12
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    int* res=malloc(numsSize*sizeof(int));
    int index=numsSize-1;
    int left=0;
    int right=numsSize-1;
    while(left<=right){
        res[index--]=nums[left]*nums[left]>=nums[right]*nums[right]?nums[left]*nums[left++]:nums[right]*nums[right--];
    }

    *returnSize=numsSize;
    return res;
}

Java代码

1
2
3
4
5
6
7
8
9
10
public int[] sortedSquares(int[] nums) {
        int[] result=new int[nums.length];
        int index=nums.length-1;
        int left=0;
        int right=nums.length-1;
        while (left<=right){
            result[index--]=(int)Math.pow(nums[left],2)>(int)Math.pow(nums[right],2)?(int)Math.pow(nums[left++],2):(int)Math.pow(nums[right--],2);
        }
        return result;
    }

image-20241104082514044