算法：有序数组的平方（Java版）

欢迎大家来到IT世界,在知识的湖畔探索吧!

有序数组的平方

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

示例：

输入: nums = [-4,-1,0,3,10] 输出: [0,1,9,16,100]

欢迎大家来到IT世界,在知识的湖畔探索吧!

暴力解法

Java代码

欢迎大家来到IT世界,在知识的湖畔探索吧!import java.util.Arrays; public class Solution { public int[] sortedSquares(int[] nums) { int n = nums.length; int[] result = new int[n]; for (int i = 0; i < n; i++) { result[i] = nums[i] * nums[i]; } Arrays.sort(result); return result; } }

时间复杂度

• 时间复杂度：O(nlogn)，其中 n 是数组的长度。这是因为 Arrays.sort() 方法通常使用一种基于归并排序或快速排序的算法，这两种算法的时间复杂度均为 O(nlogn)。

空间复杂度

• 空间复杂度：O(1)，除了输入数组和输出数组外，我们没有使用额外的空间。

双指针法

Java代码

public class Solution { public int[] sortedSquares(int[] nums) { int n = nums.length; int[] result = new int[n]; int left = 0; int 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--; } index--; } return result; } }

时间复杂度

• 时间复杂度：O(n)，其中 n 是数组的长度。因为我们只遍历了一次数组。

空间复杂度

• 空间复杂度：O(1)，除了输入数组和输出数组外，我们没有使用额外的空间。

总结

暴力解法简单直观，但时间复杂度较高。双指针法则利用了题目中数组的有序性，以空间换时间，实现了更高效的解决方案。在处理这类问题时，优先考虑是否能利用数据的特性（如有序性）来优化算法。