977. 有序数组的平方

给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例 1：

输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]
示例 2：

输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非递减顺序排序。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

image.png

数组的数值分布有三种情况。其中第一种和第三种情况，都比较容易处理。第一种情况的处理方式是平方之后直接返回，第三种情况是平方之后进行reverse即可(这是因为负数越小，则平方之后的数值越大)。
我们重点处理第二种情况。这个时候我们需要找到数组中值在0附近的元素对应的下标i。然后可以从i出发，分别向左和向右遍历数组，从而我们可以根据这两个有序数组中的元素来构造一个包含这两个数组中所有元素的新的数组。

代码

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 void pingfang(int *A,int ASize){//把数组中的元素求平方
     for(int i = 0;i< ASize;i++){
         A[i] = A[i] * A[i];
     }
 }
void reverse(int *A,int ASize){//对数组进行reverse操作
    int t = ASize/2;
    int temp;
    for(int i = 0;i<t;i++){
        temp = A[i];
        A[i] = A[ASize -1 -i];
        A[ASize -1 -i] = temp;
    }
}

int* sortedSquares(int* A, int ASize, int* returnSize){
    *returnSize = ASize;
    
    int *res = (int *)malloc( ASize * sizeof(int));
    int r = 0;
    int i = 0,j = 0;
    if(A[0] >= 0){//第一种情况
        pingfang(A,ASize);
        return A;
    }else if(A[0] < 0){
        if(A[ASize-1] <=0){//第三种情况
            pingfang(A,ASize);
            reverse(A,ASize);
            return A;
        }else{//第二种情况
            i = 0;
            while(i+1 < ASize){
                if(A[i] <= 0 && A[i+1] >=0){
                    break;
                }
                i++;
            }
            pingfang(A,ASize);
            int a = i;
            int b = i+1;
            while(a >= 0 && b < ASize){
                if(A[a] < A[b]){
                    res[r++] = A[a--];
                }else{
                    res[r++] = A[b++];
                }
            }
            while(a >= 0){
                res[r++] = A[a--];
            }
            while(b < ASize){
                res[r++] = A[b++];
            }
        }
    }
    return res;
}