【数组】有序数组的平方

做题时思路：

1. 先将数组中所有元素平方求出，然后进行排序

int* sortedSquares(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    int i = 0;
    for(i = 0;i < numsSize;i++) {
        nums[i] = nums[i]*nums[i];
    }
    bubble_sort(nums, numsSize);
    return nums;
}

void bubble_sort(int* nums, int numsSize) {
    int i = 0;
    int j = 0;
    for(i = 0;i < numsSize;i++) {
        for(j = 0;j<numsSize-i-1;j++) {
            if(nums[j+1] < nums[j]) {
                int temp = nums[j+1];
                nums[j+1] = nums[j];
                nums[j] = temp;
            }
        }
    }
}

官方思路：双指针求解

1. 数组为有序数组，但是平方后左边的负数平方有可能变成最大值了
2. 因此，我们设立两个指针front和rear，front指向0，rear指向numsSize-1
3. 创立一个新数组arr（返回结果数组）
4. 依次比较front和rear所指元素平方，哪方大就将其放入arr数组k位置。之后k-1，指针前移（front指针指的数平方较大）或后移（rear指针指的数平方较大）
5. 重复上述步骤，直到数组为满

int* sortedSquares(int* nums, int numsSize, int* returnSize){
    int* arr = (int*)malloc(numsSize*sizeof(int));
    int front = 0;
    int rear = numsSize-1;
    *returnSize = numsSize;
    int k = numsSize-1;

    int frontSquare = 0;
    int rearSquare = 0;
    for(k = numsSize-1;k>=0;k--) {
        frontSquare = nums[front]*nums[front];
        rearSquare = nums[rear]*nums[rear];
        if(frontSquare > rearSquare) {
            arr[k] = frontSquare;
            front++;
        } else {
            arr[k] = rearSquare;
            rear--;
        }
    }
    return arr;
}