| 2024-04-05 |

# 有序数组的平方

前言：这题算是第二次写了记的还是比较清楚的第一次写肯定想着暴力写法先平方再排序后面想明白了就知道从两边开始比较因为这个数组是有序的 大的一定在两边所以新的数组从两边开始

# 题目

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

示例 1：
1
2
3
4
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
1
2
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
提示：

1 <= nums.length <= 104

-104 <= nums[i] <= 104

nums 已按 非递减顺序 排序

# 题解

public class Solution {
    public int[] SortedSquares(int[] nums) {
        //从两头开始 
        int right = nums.Length-1;
        int left = 0;
        int[] result = new int[nums.Length];
        int size = nums.Length-1;
        //当左指针不再小于右指针的时候 不再循环
        while(size >= 0){ 
            //如果左平方大于右平方
            if(nums[left]*nums[left] > nums[right] * nums[right]){
                result[size] = nums[left] * nums[left];
                left++;
                size--;
            }else{
                result[size] = nums[right] * nums[right];
                right--;
                size--;
            }
        }
        return result;
    }
}

这里叭叭一下我写题的心路历程吧因为是写过的所以知道从两头开始算但奈何还是犯傻了 size 居然从 0 开始因为两边必然有一方是最大的所以肯定啊新数组从右边开始填充就是错的啊结果会变成直接平方的顺序啦。

这里我感觉还能优化一下空间复杂度不需要有一个新的数组直接覆盖试试

好嘞虽然时间不够但试试看

（你要时间多也不会花小半天弄没用的博客。。。工作还做不做了？）

（QwQ 我是真把自己当黑奴了啊）

然后就有了下面的想法

public class Solution {
    public int[] SortedSquares(int[] nums) {
        //从两头开始 
        int right = nums.Length-1;
        int left = 0;
        // int[] result = new int[nums.Length];
        int size = nums.Length-1;
        //当左指针不再小于右指针的时候 不再循环
        while(size >= 0){ 
            //如果左平方大于右平方 这时候右边会被覆盖
            if(nums[left]*nums[left] > nums[right] * nums[right]){
                nums[size] = nums[left] * nums[left];
                size--;
                nums[size] = nums[right] * nums[right];
                size--;
                left++;
                right--;
            }else{
                //右边大于左边 这时候不会被覆盖
                nums[size] = nums[right] * nums[right];
                right--;
                size--;
            }
        }
        return nums;
    }
}

很好 very good

image-20240405143814891

tags: #算法