有序数组的平方 | LeetCode-977 | 双指针

这是一道一看就会，一做就错的题目！

---

LeetCode链接：977. 有序数组的平方

---

1.题目描述

给你一个按 非递减顺序 排序的整数数组 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) 的算法解决本问题

2.题解

2.1 暴力解法

class Solution {
    public int[] sortedSquares(int[] nums) {
        //暴力解法
        //创建结果返回数组
        int[] result = new int[nums.length];
        //给数组赋值
        for(int i=0;i<nums.length;i++){
            result[i] = nums[i] * nums[i];
        }
        //排序
        //方式1：调用库函数
        //Arrays.sort(result);
        //方式2:冒泡排序
        for(int i=0;i<result.length-1;i++){
            for(int j=i+1;j<result.length;j++){
                if(result[i]>result[j]){
                    int temp = result[j];
                    result[j] = result[i];
                    result[i] = temp;
                }
            }
        }
        return result;
    }
}

2.2 双指针

class Solution {
    public int[] sortedSquares(int[] nums) {
        // 创建一个用于存储结果的数组，大小与输入数组相同
        int[] result = new int[nums.length];

        // 初始化双指针，一个指向数组的开头，另一个指向数组的结尾
        int left = 0;
        int right = nums.length - 1;
        // 初始化返回数组的索引，从最后一个位置开始填充
        int newIndex = result.length - 1;

        // 继续遍历直到左指针超过右指针
        while (left <= right) {
            // 比较左右指针对应元素的平方值
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                // 如果左指针对应元素的平方大于右指针的平方值
                // 将左指针的平方值放入返回数组的当前位置
                result[newIndex--] = nums[left] * nums[left];
                // 左指针右移
                left++;
            } else {
                // 否则，将右指针的平方值放入返回数组的当前位置
                result[newIndex--] = nums[right] * nums[right];
                // 右指针左移
                right--;
            }
        }
        // 返回排序后的平方值数组
        return result;
    }
}