LeetCode 977 - 有序数组的平方（Squares of a Sorted Array）

算法刷题>LeetCode>面试经典150
4.3k words

LeetCode 977 - 有序数组的平方

问题描述

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

进阶要求

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

解题思路

核心洞察

这道题的关键在于理解数组已排序这个重要特性。对于已排序的数组，平方后的最大值只可能出现在数组的两端：

  • 负数部分：越小的负数，平方后越大
  • 正数部分：越大的正数，平方后越大

方法一：双指针策略

利用双指针从数组两端向中间移动，比较两端的平方值，将较大的值放入结果数组的末尾：

1
2
3
4
5
6
7
原数组: [-4, -1, 0, 3, 10]
        ↑              ↑
       left           right

平方后: [16,  1, 0, 9, 100]
        ↑              ↑
       left           right

算法步骤：

  1. 初始化两个指针：left = 0，right = n - 1
  2. 初始化结果数组 result，长度为 n
  3. 从右到左填充结果数组：
    • 比较 nums[left]^2 和 nums[right]^2
    • 将较大的值放入 result[index]
    • 移动相应的指针
  4. 重复直到所有位置都被填充

方法二：归并排序思想

这种方法更好地利用了「数组已排序」的特性：

  1. 找到分界线：确定负数与非负数的分界点 neg
  2. 分析平方后的特性：
    • 负数部分平方后：nums[0]^2 到 nums[neg]^2 单调递减
    • 正数部分平方后：nums[neg+1]^2 到 nums[n-1]^2 单调递增
  3. 归并两个有序子数组：使用两个指针分别指向分界线两侧
1
2
3
4
5
6
7
原数组: [-4, -1, 0, 3, 10]
              ↑
           分界线

平方后: [16,  1, 0, 9, 100]
        ↓    ↓  ↑  ↑   ↑
      递减  递减 递增 递增 递增

为什么这些方法有效？

双指针方法：

  • 如果 |nums[left]| > |nums[right]|，那么 nums[left]^2 一定大于 nums[right]^2
  • 如果 |nums[left]| <= |nums[right]|，那么 nums[right]^2 一定大于等于 nums[left]^2

归并排序思想：

  • 充分利用了数组已排序的特性
  • 平方后的两个子数组都是有序的，可以直接归并
  • 逻辑更加清晰，更容易理解和实现

实现细节

关键实现要点

  1. 绝对值比较：比较 abs(nums[left]) 和 abs(nums[right]) 而不是直接比较平方值，避免溢出
  2. 从右到左填充：确保结果数组按非递减顺序排列
  3. 指针移动：根据比较结果移动相应的指针

执行过程示例

双指针方法

以 nums = [-4, -1, 0, 3, 10] 为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Step 1: left=0, right=4, index=4
        |nums[0]| = 4, |nums[4]| = 10
        4 < 10, 所以 nums[4]^2 = 100 更大
        result[4] = 100, right--

Step 2: left=0, right=3, index=3
        |nums[0]| = 4, |nums[3]| = 3
        4 > 3, 所以 nums[0]^2 = 16 更大
        result[3] = 16, left++

Step 3: left=1, right=3, index=2
        |nums[1]| = 1, |nums[3]| = 3
        1 < 3, 所以 nums[3]^2 = 9 更大
        result[2] = 9, right--

Step 4: left=1, right=2, index=1
        |nums[1]| = 1, |nums[2]| = 0
        1 > 0, 所以 nums[1]^2 = 1 更大
        result[1] = 1, left++

Step 5: left=2, right=2, index=0
        |nums[2]| = 0, |nums[2]| = 0
        相等，取任意一个
        result[0] = 0

最终结果: [0, 1, 9, 16, 100]

归并排序思想

以 nums = [-4, -1, 0, 3, 10] 为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Step 1: 找分界线
        negative = 1 (nums[1] = -1 是最后一个负数)

Step 2: 初始化指针
        i = 1 (指向最后一个负数)
        j = 2 (指向第一个非负数)
        index = 0

Step 3: 归并过程
        i=1, j=2: nums[1]^2=1, nums[2]^2=0
        1 > 0, 选择 nums[2]^2=0
        result[0] = 0, j++, index++

        i=1, j=3: nums[1]^2=1, nums[3]^2=9
        1 < 9, 选择 nums[1]^2=1
        result[1] = 1, i--, index++

        i=0, j=3: nums[0]^2=16, nums[3]^2=9
        16 > 9, 选择 nums[3]^2=9
        result[2] = 9, j++, index++

        i=0, j=4: nums[0]^2=16, nums[4]^2=100
        16 < 100, 选择 nums[0]^2=16
        result[3] = 16, i--, index++

        i=-1, j=4: 负数部分已处理完
        result[4] = 100, j++, index++

最终结果: [0, 1, 9, 16, 100]

代码实现

方法一：双指针（推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int[] sortedSquares(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    int left = 0, right = n - 1;
    int index = n - 1;
    
    while (left <= right) {
        // 比较绝对值，避免溢出
        if (Math.abs(nums[left]) > Math.abs(nums[right])) {
            result[index] = nums[left] * nums[left];
            left++;
        } else {
            result[index] = nums[right] * nums[right];
            right--;
        }
        index--;
    }
    
    return result;
}

方法二：归并排序思想（推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public int[] sortedSquares(int[] nums) {
    int n = nums.length;
    int negative = -1;
    
    // 找到负数与非负数的分界线
    for (int i = 0; i < n; ++i) {
        if (nums[i] < 0) {
            negative = i;
        } else {
            break;
        }
    }

    int[] ans = new int[n];
    int index = 0, i = negative, j = negative + 1;
    
    // 归并两个有序子数组
    while (i >= 0 || j < n) {
        if (i < 0) {
            // 负数部分已处理完，直接添加正数部分
            ans[index] = nums[j] * nums[j];
            ++j;
        } else if (j == n) {
            // 正数部分已处理完，直接添加负数部分
            ans[index] = nums[i] * nums[i];
            --i;
        } else if (nums[i] * nums[i] < nums[j] * nums[j]) {
            // 负数平方更小，选择负数
            ans[index] = nums[i] * nums[i];
            --i;
        } else {
            // 正数平方更小，选择正数
            ans[index] = nums[j] * nums[j];
            ++j;
        }
        ++index;
    }

    return ans;
}

方法三：先平方后排序（不推荐）

1
2
3
4
5
6
7
8
9
10
11
public int[] sortedSquares(int[] nums) {
    // 先计算所有元素的平方
    for (int i = 0; i < nums.length; i++) {
        nums[i] = nums[i] * nums[i];
    }
    
    // 然后排序
    Arrays.sort(nums);
    
    return nums;
}

方法比较

方面 双指针方法 归并排序思想 先平方后排序
时间复杂度 $O(n)$ $O(n)$ $O(n \log n)$
空间复杂度 $O(n)$ $O(n)$ $O(1)$
优点 高效，代码简洁 更好地利用数组特性，逻辑清晰 实现简单
缺点 需要额外空间 需要额外空间，代码稍复杂 时间复杂度较高
推荐度 ★★★★★ ★★★★☆ ★★☆☆☆

复杂度分析

时间复杂度

双指针方法： $O(n)$

  • 每个元素只被访问一次
  • 总共进行 $n$ 次比较和赋值操作

归并排序思想： $O(n)$

  • 找分界线：$O(n)$
  • 归并过程：$O(n)$
  • 总体：$O(n)$

先平方后排序： $O(n \log n)$

  • 平方操作：$O(n)$
  • 排序操作：$O(n \log n)$
  • 总体：$O(n \log n)$

空间复杂度

双指针方法： $O(n)$

  • 需要额外的结果数组存储平方后的值

归并排序思想： $O(n)$

  • 需要额外的结果数组存储平方后的值

先平方后排序： $O(1)$

  • 原地修改原数组（如果允许修改原数组）

关键收获

核心算法思想

  1. 利用数据特性：充分利用”数组已排序”这一重要信息
  2. 双指针技巧：从两端向中间移动，避免不必要的比较
  3. 归并排序思想：将问题分解为两个有序子数组的归并
  4. 贪心策略：每次选择当前最大（或最小）的平方值

常见陷阱

  1. 直接比较平方值：可能导致整数溢出，应比较绝对值
  2. 忽略边界条件：确保循环条件 left <= right 正确处理所有情况
  3. 填充顺序错误：必须从右到左填充结果数组

相关问题

实际应用

  • 信号处理：对信号数据进行平方运算并保持有序性
  • 数据分析：计算方差时需要保持数据的相对顺序
  • 图形学：计算距离的平方时保持排序特性

总结：这道题是双指针技巧的经典应用，通过利用数组已排序的特性，我们可以在 $O(n)$ 时间内解决问题，避免了 $O(n \log n)$ 的排序开销。关键在于理解平方后的最大值只可能出现在数组的两端，从而设计出高效的双指针算法。