当前位置：首页 > article >正文

【ARTS】【LeetCode-977】有序数组的平方

article 2025/2/21 10:25:10

前言

仅做学习使用，侵删

什么是ARTS？

算法(Algorithm): 每周至少一道LeetCode算法题，加强编程训练和算法学习

阅读(Review)：阅读并点评至少一篇英文技术文章，提高英文水平

技巧 (Tip)：学习至少一个技术技巧，总结、归纳日常工作中遇到的知识点

分享(Share)：分析一篇有关点和思考的技术文章，建立影响力，输出价值观

算法

力扣-977题

977. 有序数组的平方 - 力扣（LeetCode）

题目描述

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

进阶：

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

前置知识

数组操作：了解如何遍历数组、修改数组元素。

数组的基础知识可以看这里程序员算法面试中，必须掌握的数组理论知识 (opens new window)

双指针技巧：掌握使用两个指针来处理数组问题的方法，其中一个用于读取（遍历），另一个用于写入（记录有效位置）

具体参考【ARTS】【LeetCode-27】移除元素-CSDN博客

解题方法

方法一:暴力求解

最直接最简单的想法：对数组内的每个数平方后排序

class Solution {
    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)，其中 n 是数组的长度。
使用了 Arrays.sort() 方法对数组进行排序。在 Java 中，Arrays.sort() 对基本类型数组（如 int[]）使用的是双轴快速排序（Dual-pivot Quicksort），其平均时间复杂度为 O(n log n)，在最坏情况下是 O(n²)。但现代 Java 实现中，双轴快速排序对大数据集的表现通常较好，时间复杂度可以近似为 O(n log n)。
总时间复杂度：将两者相加，主要由排序部分主导，因此总时间复杂度为 O(n log n)。

空间复杂度：

代码直接在输入数组上进行操作，没有创建额外的数组即O(log n)。

方法二：双指针法

读题：需要将非递减排列的整数数组平方后，同样按非递减顺序排序。关键在于利用数组已排序的特性，通过双指针法在 O(n) 时间复杂度内完成

方法思路

双指针策略：

由于原数组有序，平方后的最大值可能出现在数组两端。使用左右指针分别指向数组的起始和末尾。

逆向填充：

从结果数组的末尾开始填充，每次比较左右指针指向元素的平方，将较大者放入当前结果位置，并移动相应指针。

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) {
        int leftSquare = nums[left] * nums[left];
        int rightSquare = nums[right] * nums[right];
        
        if (leftSquare > rightSquare) {
            result[index--] = leftSquare;
            left++;
        } else {
            result[index--] = rightSquare;
            right--;
        }
    }
    return result;
}

代码解释

初始化指针：left 指向数组起始，right 指向数组末尾，index 用于从后向前填充结果数组。

循环比较：每次计算左右指针所指元素的平方，将较大的值放入结果数组的当前末尾位置，并移动对应的指针。

该方法巧妙利用数组的有序性，避免了传统排序的 O(n log n) 时间复杂度，实现了线性时间的解决方案。