题目 ——Leecode:977. 有序数组的平方

目录

题目 ——Leecode:977. 有序数组的平方

题目分析

暴力解法：

双指针解法：

---

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

题目分析

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组.

题目说的有序数组，有三种情况。

（1）全是负数

-6，-5，-4，-3，-2

（2）全是正数

1，3，4，5，6，7

（3）有正有负

-3，-2，0，5，6，7

不管那种情况元素的平方最大值一定产生在原数组的最左边或者最右边。

暴力解法：

 public int[] sortedSquares01(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] * nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }

我们会发现，暴力解法为两步：①先把数组中的元素变为平方。②将变为平方的数组排序。

这种解法依赖于java类库的排序。5

时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。

空间复杂度：O(logn)。除了存储答案的数组以外，我们需要 O(logn) 的栈空间进行排序。

双指针解法：

暴力解法没有利用「数组 nums 已经按照升序排序」这个条件。下面采用双指针的方法：

        使用两个指针分别指向位置 0 和 lenglength−1，每次比较两个指针对应的数，选择较大的那个逆序放入新数组并移动指针。这种方法无需处理某一指针移动至边界的情况.

class Solution {
    public int[] sortedSquares(int[] nums) {

        int size=nums.length;
        // 左指针，指向原数组最左边
        int left=0;
        // 右指针，指向原数组最右边
        int right=size-1;

        //定义新数组，存平方后的值
        int[] square=new int[size];
        // 得到元素值平方值，从新数组最后位置开始写
        int size2=nums.length-1;

        while(left<=right){
            if(nums[left]*nums[left]>nums[right]*nums[right]){
                square[size2]=nums[left]*nums[left];
                left++;
                size2--;
            }else{
                 square[size2]=nums[right]*nums[right];
                 right--;
                 size2--;
            }
        }
        return square;
    }
}

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。

• 空间复杂度：O(1)。除了存储答案的数组以外，我们只需要维护常量空间。