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] <= 104nums已按 非递减顺序 排序
【算法设计思想】
在本题中，利用双指针法可以高效地解决这个问题。由于输入数组已经按非递减顺序排序，因此最大的平方值只会出现在数组的两端（即最小的负数的平方或最大的正数的平方）。
【算法描述】
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; // 返回结果数组
}