[数据结构与算法]LeetCode——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) 的算法解决本问题

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array

二、思路

• 思路一：先对数组中每个数字全部进行平方，然后进行一次排序，这样的时间复杂度为max{平方的时间复杂度On+排序的时间复杂度}，最低也是Onlog的级别
• 思路二：先找到负数和正数的分界点，使用两个指针，一个指针往负数走，一个往正数走，每次比较两个指针指向元素的绝对值大小，绝对值小的数字进行平方后放进ans数组中，然后此指针加一，直到一个指针走到尽头，再将最后一个指针指向的每一个元素全部加入到ans数组中。时间复杂度为查找分界点On+快慢指针移动到头的时间On，时间复杂度为On级别

三、C语言代码

思路二：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* sortedSquares(int* nums, int numsSize, int* returnSize){
     
    int* ans = (int *) malloc(numsSize*sizeof(int));
    int left=0,right=0,count=0;
    while(nums[right]<0&&right<numsSize-1) right++;
    left = right-1;
    while(left>-1&&right!=numsSize){
        if(abs(nums[left])>abs(nums[right])) {
            ans[count] = nums[right]*nums[right];
            right++;count++;
        }
        else {
            ans[count] = nums[left]*nums[left];
            left--;count++;
        }
    }
    while(left>-1) {
            ans[count] = nums[left]*nums[left];
            left--;count++;
        }
    while(right!=numsSize) {
            ans[count] = nums[right]*nums[right];
            right++;count++;
        }
    *returnSize = count;
    return ans;
}