题目描述

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

代码实现

归并做法 时间复杂度O(n)

//找到正负分界点，平方后归并
class Solution {
    public int[] sortedSquares(int[] nums) {
        //找出分界点
        int negative=-1;
        int n = nums.length;
        for(int i = n-1 ; i>=0 ; i--){
            if(nums[i]<0) {negative=i;break;}
        }
        //平方
        for(int i = 0 ; i<n;i++){
            nums[i]=nums[i]*nums[i];
        }
        //归并排序
        int ans[]=new int[n];
        int i = 0 ; 
        int l=negative,r=negative+1;
        while(l>=0 && r <= n-1){
            if(nums[l]>=nums[r]){
                ans[i++]=nums[r++];
            }else{ans[i++]=nums[l--];}
        }
        while(l>=0) {ans[i++]=nums[l--];}
        while(r<=n-1){ans[i++]=nums[r++];}

        return ans;
    }
}

排序做法 时间复杂度O(nlogn) 代码略