🍎道阻且长，行则将至。🍓

🌻算法，不如说它是一种思考方式🍀

算法专栏： 👉🏻123

一、🌱977. 有序数组的平方

• 题目描述：给你一个按==非递减顺序==排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
• 来源：力扣（LeetCode）
• 难度：简单
• 提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
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]

*进阶：
请你设计==时间复杂度为 O(n) 的算法==解决本问题

🌴解题

1.直接排序

最简单的想法：直接对数组平方后排序，而排序算法中的快速排序时间复杂度达到O(nlogn)。

2.双指针

这个问题只是由于前面部分的负数影响我们的结果，在负数那一块在前面的更大，所以可以在前后双指针往中间遍历，（先找大的）对比平方值从后往前存入结果中，就可以完成。

code:

class Solution {
    public int[] sortedSquares(int[] nums) {
                int i=0;
        int end =nums.length;
        int[] ans=new int[end];

        end--;
        int k=end;
        while(i <= end) {
            if(nums[i]*nums[i]<nums[end]*nums[end]){
                ans[k]=nums[end]*nums[end];
                end--;k--;
            }
            else{
                ans[k]=nums[i]*nums[i];
                i++;k--;
            }

        }
        return ans;

    }
}

那么我们也可以从中间开始，先找到最小的：

code:

class Solution {
public int[] sortedSquares(int[] nums) {
        int n=nums.length;
        int[] ans=new int[n];
        if(nums[0]>=0){
            insert(nums,ans,0);
        }else{
            for (int i = 0; i < n; i++) {//找到第一个非负数
                if(nums[i]>=0){
                    insert(nums,ans,i);
                    break;
                }
                else if(i==n-1){//都是负数
                    insert(nums,ans,i+1);
                    break;
                }

            }

        }
        return ans;
    }

    private static void insert(int[] nums, int[] ans, int i) {
        int j=i-1;
        int k=0;
        while (j >=0&&i<nums.length) {
            if(j<0)break;
            //前面的小
            if(-nums[j]<nums[i]){
                ans[k]=nums[j]*nums[j];
                j--;k++;
            }else{
                ans[k]=nums[i]*nums[i];
                i++;k++;
            }
        }
        while(j>=0) {
            ans[k]=nums[j]*nums[j];
            j--;k++;
        }
        while(i<nums.length) {
            ans[k]=nums[i]*nums[i];
            i++;k++;
        }
    }
}

☕物有本末，事有终始，知所先后。🍭