Leetcode 977.有序数组的平方(画图分析)

力扣传送门(opens new window)

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

解题思路：

双指针法。

我们可以准备 left 和 right 两个指针，一个从数组的头部出发，一个从数组的尾部出发

接着我们准备一个新的数组，用来保存最后的结果，数组的长度为原来数组的长度

接着我们比较nums[left]和nums[right]的平方，哪一个大，我们就把他放到新数组的倒数最后一个空的位置

直到 left==right。

这样遍历完整个数组后，我们就得到了一个新的数组，并且按照从小到大的顺序排列

代码实现：

java

class Solution {
    public int[] sortedSquares(int[] nums) {
        // 数组长度
        int n = nums.length;  
        // 结果数组
        int[] ans = new int[n];  
        int left = 0;
        int right = nums.length -1;
        int pos = nums.length -1;
        while(left <= right){
            // 比较数组左右两端的平方值大小
            if (nums[left] * nums[left] > nums[right] * nums[right]) {  
                // 将较大的平方值放入结果数组中
                ans[pos] = nums[left] * nums[left];  
                // 左指针向右移动一位
                ++left;  
            } else {
                // 将较大的平方值放入结果数组中
                ans[pos] = nums[right] * nums[right];  
                // 右指针向左移动一位
                --right;  
            }
            // 结果数组的下标向前移动一位
            --pos;  
        }
        // 返回结果数组
        return ans;  
    }
}

python3

class Solution:
    def sortedSquares(self, nums):
        # 数组长度
        n = len(nums)
        # 结果数组
        ans = [0] * n
        left = 0
        right = len(nums) - 1
        pos = len(nums) - 1
      
        while left <= right:
            # 比较数组左右两端的平方值大小
            if nums[left] * nums[left] > nums[right] * nums[right]:
                # 将较大的平方值放入结果数组中
                ans[pos] = nums[left] * nums[left]
                # 左指针向右移动一位
                left += 1
            else:
                # 将较大的平方值放入结果数组中
                ans[pos] = nums[right] * nums[right]
                # 右指针向左移动一位
                right -= 1
            # 结果数组的下标向前移动一位
            pos -= 1
      
        # 返回结果数组
        return ans

c++

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        // 数组长度
        int n = nums.size();
        // 结果数组
        vector<int> ans(n); 
        int left = 0;
        int right = nums.size() - 1;
        int pos = nums.size() - 1;
      
        while (left <= right) {
            // 比较数组左右两端的平方值大小
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                // 将较大的平方值放入结果数组中
                ans[pos] = nums[left] * nums[left];
                // 左指针向右移动一位
                left++;
            } else {
                // 将较大的平方值放入结果数组中
                ans[pos] = nums[right] * nums[right];
                // 右指针向左移动一位
                right--;
            }
            // 结果数组的下标向前移动一位
            pos--;
        }
      
        // 返回结果数组
        return ans;
    }
};