有序数组的平方

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

示例：

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

暴力解法

Java代码

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)，除了输入数组和输出数组外，我们没有使用额外的空间。

总结

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