数组——977. 有序数组的平方

拼搏现实的明天。 2023-10-08 16:04 20阅读 0赞

## 1 题目描述 ##

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

## 2 题目示例 ##

示例 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\]

## 3 题目提示 ##

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

## 4 思路 ##

数组其实是有序的， 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，i指向起始位置，j指向终止位置。

定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

## 5 我的答案 ##

class Solution {
        
        public int[] sortedSquares(int[] nums) {
        
            int right = nums.length - 1;
            int left = 0;
            int[] result = new int[nums.length];
            int index = result.length - 1;
            while (left <= right) {
        
                if (nums[left] * nums[left] > nums[right] * nums[right]) {
        
                    // 正数的相对位置是不变的， 需要调整的是负数平方后的相对位置
                    result[index--] = nums[left] * nums[left];
                    ++left;
                } else {
        
                    result[index--] = nums[right] * nums[right];
                    --right;
                }
            }
            return result;
        }
    }

class Solution {
        
        public int[] sortedSquares(int[] nums) {
        
            int l = 0;
            int r = nums.length - 1;
            int[] res = new int[nums.length];
            int j = nums.length - 1;
            while(l <= r){
        
                if(nums[l] * nums[l] > nums[r] * nums[r]){
        
                    res[j--] = nums[l] * nums[l++];
                }else{
        
                    res[j--] = nums[r] * nums[r--];
                }
            }
            return res;
        }
    }