977_有序数组的平方

【问题描述】

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

示例一：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例二：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序

【算法设计思想】

在本题中，利用双指针法可以高效地解决这个问题。由于输入数组已经按非递减顺序排序，因此最大的平方值只会出现在数组的两端（即最小的负数的平方或最大的正数的平方）。

【算法描述】

C++：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();  // 获取数组的长度
        int left = 0;         // 初始化左指针，指向数组的起始位置
        int right = n - 1;    // 初始化右指针，指向数组的结束位置
        int pos = n - 1;      // 初始化结果数组的当前位置，从最后一个位置开始
        vector<int> result(n, -1);  // 初始化结果数组，大小与输入数组相同，初始值为 -1

        while (left <= right) {  // 当左指针小于等于右指针时，继续循环
            if (nums[left] * nums[left] >= nums[right] * nums[right]) {
                // 如果左指针所指元素的平方大于或等于右指针所指元素的平方
                result[pos] = nums[left] * nums[left];  // 将左指针所指元素的平方值放入结果数组的当前位置
                left++;  // 左指针向右移动一位
            } else {
                // 如果右指针所指元素的平方大于左指针所指元素的平方
                result[pos] = nums[right] * nums[right];  // 将右指针所指元素的平方值放入结果数组的当前位置
                right--;  // 右指针向左移动一位
            }
            pos--;  // 结果数组的当前位置向前移动一位
        }

        return result;  // 返回结果数组
    }
};

Java：

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;  // 获取数组的长度
        int left = 0;         // 初始化左指针，指向数组的起始位置
        int right = n - 1;    // 初始化右指针，指向数组的结束位置
        int pos = n - 1;      // 初始化结果数组的当前位置，从最后一个位置开始
        int[] result = new int[n];  // 初始化结果数组，大小与输入数组相同

        while (left <= right) {  // 当左指针小于等于右指针时，继续循环
            if (nums[left] * nums[left] >= nums[right] * nums[right]) {
                // 如果左指针所指元素的平方大于或等于右指针所指元素的平方
                result[pos] = nums[left] * nums[left];  // 将左指针所指元素的平方值放入结果数组的当前位置
                left++;  // 左指针向右移动一位
            } else {
                // 如果右指针所指元素的平方大于左指针所指元素的平方
                result[pos] = nums[right] * nums[right];  // 将右指针所指元素的平方值放入结果数组的当前位置
                right--;  // 右指针向左移动一位
            }
            pos--;  // 结果数组的当前位置向前移动一位
        }

        return result;  // 返回结果数组
    }
}

Python：

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)  # 获取数组的长度
        left = 0  # 初始化左指针，指向数组的起始位置
        right = n - 1  # 初始化右指针，指向数组的结束位置
        pos = n - 1  # 初始化结果数组的当前位置，从最后一个位置开始
        result = [-1] * n  # 初始化结果数组，大小与输入数组相同，初始值为 -1

        while left <= right:  # 当左指针小于等于右指针时，继续循环
            left_square = nums[left] ** 2  # 计算左指针所指元素的平方
            right_square = nums[right] ** 2  # 计算右指针所指元素的平方

            if left_square >= right_square:
                # 如果左指针所指元素的平方大于或等于右指针所指元素的平方
                result[pos] = left_square  # 将左指针所指元素的平方值放入结果数组的当前位置
                left += 1  # 左指针向右移动一位
            else:
                # 如果右指针所指元素的平方大于左指针所指元素的平方
                result[pos] = right_square  # 将右指针所指元素的平方值放入结果数组的当前位置
                right -= 1  # 右指针向左移动一位

            pos -= 1  # 结果数组的当前位置向前移动一位

        return result  # 返回结果数组

C：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    int left = 0;  // 初始化左指针，指向数组的起始位置
    int right = numsSize - 1;  // 初始化右指针，指向数组的结束位置
    int pos = numsSize - 1;  // 初始化结果数组的当前位置，从最后一个位置开始

    // 动态分配结果数组的内存
    int* result = (int*)malloc(numsSize * sizeof(int));
    if (result == NULL) {
        // 内存分配失败，返回 NULL 并设置 returnSize 为 0
        *returnSize = 0;
        return NULL;
    }

    while (left <= right) {  // 当左指针小于等于右指针时，继续循环
        int leftSquare = nums[left] * nums[left];  // 计算左指针所指元素的平方
        int rightSquare = nums[right] * nums[right];  // 计算右指针所指元素的平方

        if (leftSquare >= rightSquare) {
            // 如果左指针所指元素的平方大于或等于右指针所指元素的平方
            result[pos] = leftSquare;  // 将左指针所指元素的平方值放入结果数组的当前位置
            left++;  // 左指针向右移动一位
        } else {
            // 如果右指针所指元素的平方大于左指针所指元素的平方
            result[pos] = rightSquare;  // 将右指针所指元素的平方值放入结果数组的当前位置
            right--;  // 右指针向左移动一位
        }
        pos--;  // 结果数组的当前位置向前移动一位
    }

    *returnSize = numsSize;  // 设置返回数组的大小
    return result;  // 返回结果数组
}