力扣No.977 有序数组的平方题解：直接排序+双指针

题目描述

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

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

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

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序

进阶：

• 请你设计时间复杂度为 O(n) 的算法解决本问题

直接排序

这题是一个简单题，起初我使用的方式是直接暴力的排序法，也就是遍历原始数组，将每一个元素平方之后存入结果数组，然后使用qsort对原始数组进行排序。

代码：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int compare(const void* _a,const void* _b){
    int a = *(int*)_a;
    int b = *(int*)_b;
    return a-b; //返回-1
}
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    (*returnSize) = numsSize;
    int* res = malloc(sizeof(int) * numsSize);
    for(int i = 0;i<numsSize;i++){
        res[i]=nums[i]*nums[i];
    }
    qsort(res,numsSize,sizeof(int),compare);
    return res;
}

这样来实现算法具有良好的通用性，不仅针对有序数组的平方，即使是无序数组的平方也能够得到升序排序的结果。

但是针对本题来看，使用直接排序的方法就没有利用到题目中给定的所有元素都是按非降序排序的。也就是原始数组的元素已经按照升序排序了，利用这个条件就可以推导出以下隐含条件：

1. 数组中的负数平方后是降序的，正数平方后是升序的。
2. 数组边界的元素的平方是最大的（比较0和len-1的元素大小得到最大值）

因此，本题还可以通过双指针的方法求解。

双指针

由于数组的边界值是最大的，且数组中正负数经过平方后是相反的排序，可以通过双指针的方式，从数组的开头和结尾开始遍历数组，当找到一个平方后最大的值，将这个值插入到结果数组的最后一位，每次插值将结果数组的下标向前移动一位，通过将对应的指针自增或者自减。

当两个指针指向的位置重合或者颠倒之后，则数组已经被遍历完成。

代码：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    int* ans = malloc(sizeof(int)*numsSize);
    *returnSize = numsSize;
    for(int i =0,j=numsSize-1,pos=numsSize-1;i<=j;){
        if(nums[i]*nums[i]>nums[j]*nums[j]){
            ans[pos]=nums[i]*nums[i];
            i++;
        }else{
            ans[pos]=nums[j]*nums[j];
            j--;
        }
        pos--;
    }
    return ans;
}