Easy

题目描述

给你一个按 非递减顺序 排序的整数数组 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) 的算法解决本问题

解题思路

解题思路

这道题有两种主要解法：

方法一：直接平方后排序

最直观的方法是对每个元素平方，然后排序。时间复杂度为 O(n log n)。

方法二：双指针（推荐）

由于原数组已经有序，我们可以利用这个特性。观察发现，平方后最大的元素一定出现在数组的两端（最小的负数或最大的正数）。

使用双指针技巧：

  • 左指针指向数组开头，右指针指向数组末尾
  • 比较两端元素的平方值大小
  • 将较大的平方值放入结果数组的末尾
  • 移动对应指针，继续比较
  • 从后向前填充结果数组

这样可以在 O(n) 时间内完成，且只需要 O(1) 额外空间（不考虑结果数组）。

核心思想是利用原数组的有序性，通过双指针从两端向中间收缩，每次选择平方值较大的元素放入结果数组。

代码实现

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

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [0] * n
        left, right = 0, n - 1
        pos = n - 1
        
        while left <= right:
            left_square = nums[left] ** 2
            right_square = nums[right] ** 2
            
            if left_square > right_square:
                result[pos] = left_square
                left += 1
            else:
                result[pos] = right_square
                right -= 1
            pos -= 1
            
        return result

public class Solution {
    public int[] SortedSquares(int[] nums) {
        int n = nums.Length;
        int[] result = new int[n];
        int left = 0, right = n - 1;
        int pos = n - 1;
        
        while (left <= right) {
            int leftSquare = nums[left] * nums[left];
            int rightSquare = nums[right] * nums[right];
            
            if (leftSquare > rightSquare) {
                result[pos] = leftSquare;
                left++;
            } else {
                result[pos] = rightSquare;
                right--;
            }
            pos--;
        }
        
        return result;
    }
}

var sortedSquares = function(nums) {
    const n = nums.length;
    const result = new Array(n);
    let left = 0, right = n - 1;
    let pos = n - 1;
    
    while (left <= right) {
        const leftSquare = nums[left] * nums[left];
        const rightSquare = nums[right] * nums[right];
        
        if (leftSquare > rightSquare) {
            result[pos] = leftSquare;
            left++;
        } else {
            result[pos] = rightSquare;
            right--;
        }
        pos--;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型双指针解法直接排序解法
时间复杂度O(n)O(n log n)
空间复杂度O(1)O(1)

注：空间复杂度不包括结果数组的存储空间

相关题目