0977-有序数组的平方

题目链接

题目描述

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

示例

示例1：

输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100] 排序后，数组变为 [0,1,9,16,100]

提示

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

• nums 已按 非递减顺序 排序

  思路

  思路1：排序

  平方后排序。

  思路2：双指针

  对于一个数组 nums 来说，平方的最大值只能在头部或尾部产生。考虑一般情况，即数组中有负数，0,和正数，维护两个指针 left = 0 和 right = n - 1 ：

• 两个指针相向移动的过程中，比较两数平方，将较大者加入数组 ans 中。

• 数组 ans 逆序遍历。

一点优化：比较平方 if(nums[left] * nums[left] < nums[right] * nums[right]) 可以优化为 if(-nums[left] < nums[right])，可以减少乘法运算。
此做法的正确性是可以证明的：
为了表示简单，我们设 ，分类讨论：

• ，由 nums 非递减可知 ，此时恒有 ，且
• ，由 nums 非递减可知 ，此时恒有 ，且
• 若 异号，则只有 ，若 ，有 ；若 ，有

综上所诉，两者是等价的。

题解

思路2：双指针

class Solution {
   public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        int left = 0, right = n - 1;
        int i = n - 1;
        vector<int> ans(n);
        while (left <= right) {
            if (-nums[left] < nums[right]) {
                ans[i--] = nums[right] * nums[right];
                --right;
            } else {
                ans[i--] = nums[left] * nums[left];
                ++left;
            }
        }
        return ans;
    }
};

复杂度分析

思路2：双指针

• 时间复杂度：
• 空间复杂度：