977-有序数组的平方

题目地址(977. 有序数组的平方 - 力扣（LeetCode）)

https://leetcode.cn/problems/squares-of-a-sorted-array/description/

题目描述

给你一个按 非递减顺序 排序的整数数组 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 <= 10 4
• -10 4 <= nums [i] <= 10 4
• nums 已按 非递减顺序 排序

 

进阶：

• 请你 设计时间复杂度为 O(n) 的算法解决本问题

前置知识

• 双指针

思路

使用两个指针分别指向位置 $0$ 和 $n−1$，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。

关键点

• 平方大小的比较 = 绝对值大小的比较
• 双指针指向相等时，任意放一个进入结果数组即可。

代码

• 语言支持：Java

Java Code:

class Solution {
    public int[] sortedSquares(int[] nums) {
// 非递减
      // 在正数，越大，平方也就越大
      // 在负数，越小，平方越大
      // 采用双指针，头尾比较
      int left = 0;
      int right = nums.length - 1;
      int[] ret = new int[nums.length];
      int index = right;
      while (left < right) { // 当left == right时，退出循环
        if (Math.abs(nums[left]) < Math.abs(nums[right])) {
          ret[index--] = nums[right] * nums[right];
          right--;
        } else if (Math.abs(nums[left]) > Math.abs(nums[right])) {
          ret[index--] = nums[left]*nums[left];
          left++;
        }else if(Math.abs(nums[left]) == Math.abs(nums[right])){
          ret[index--] = nums[right]*nums[right];
          right--;
        }
      }
      ret[index] = nums[left]*nums[left];
      return ret;
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$，除了存储答案的数组以外，我们只需要维护常量空间。