给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
- 输入：nums = [-4,-1,0,3,10]
- 输出：[0,1,9,16,100]
- 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]
示例 2：
- 输出：[4,9,9,49,121]
- 输入：nums = [-7,-3,2,3,11]
C++ 实现
#include <vector>
#include <algorithm>
using namespace std;
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
vector<int> result(n);
int left = 0, right = n - 1;
for (int i = n - 1; i >= 0; i--) {
if (abs(nums[left]) > abs(nums[right])) {
result[i] = nums[left] * nums[left];
left++;
}
else {
result[i] = nums[right] * nums[right];
right--;
}
}
return result;
}代码说明：
- 双指针法：利用原数组已按非递减顺序排序的特性，使用两个指针分别指向数组的首尾元素。
- 平方比较：比较首尾元素的绝对值大小，将较大值的平方放入结果数组的末尾。
- 逆序填充：从结果数组的最后位置开始填充，确保生成的新数组按非递减顺序排列。
复杂度分析：
- 时间复杂度：O (n)，仅需遍历一次数组。
- 空间复杂度：O (n)，主要用于存储结果数组。
#include <iostream>
#include <vector>
using namespace std;
vector<int> sortedSquares(vector<int>& nums); // 假设已实现该函数
int main() {
// 测试用例1：包含正负元素
vector<int> nums1 = {-4, -1, 0, 3, 10};
vector<int> result1 = sortedSquares(nums1);
cout << "测试用例1: ";
for (int num : result1) cout << num << " "; // 输出: 0 1 9 16 100
cout << endl;
// 测试用例2：全负数
vector<int> nums2 = {-7, -3, -2};
vector<int> result2 = sortedSquares(nums2);
cout << "测试用例2: ";
for (int num : result2) cout << num << " "; // 输出: 4 9 49
cout << endl;
// 测试用例3：全正数
vector<int> nums3 = {2, 3, 11};
vector<int> result3 = sortedSquares(nums3);
cout << "测试用例3: ";
for (int num : result3) cout << num << " "; // 输出: 4 9 121
cout << endl;
// 测试用例4：包含0
vector<int> nums4 = {-5, 0, 5};
vector<int> result4 = sortedSquares(nums4);
cout << "测试用例4: ";
for (int num : result4) cout << num << " "; // 输出: 0 25 25
cout << endl;
// 测试用例5：单元素
vector<int> nums5 = {7};
vector<int> result5 = sortedSquares(nums5);
cout << "测试用例5: ";
for (int num : result5) cout << num << " "; // 输出: 49
cout << endl;
return 0;
}测试说明：
- 测试用例 1：验证正负混合元素的处理，确保平方后按升序排列。
- 测试用例 2：验证全负数数组的处理，平方后应为递增顺序。
- 测试用例 3：验证全正数数组的处理，平方后保持原顺序。
- 测试用例 4：验证包含 0 的数组，确保 0 在正确位置。
- 测试用例 5：验证边界情况（单元素数组）。
C语言实现
#include <stdlib.h>
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
int* result = (int*)malloc(numsSize * sizeof(int));
*returnSize = numsSize;
int left = 0;
int right = numsSize - 1;
for (int i = numsSize - 1; i >= 0; i--) {
if (abs(nums[left]) > abs(nums[right])) {
result[i] = nums[left] * nums[left];
left++;
} else {
result[i] = nums[right] * nums[right];
right--;
}
}
return result;
}代码说明：
- 内存分配：动态分配结果数组，大小与输入数组相同。
- 双指针法：通过左右指针分别指向数组首尾，比较绝对值大小后逆序填充结果数组。
- 返回值处理：通过
returnSize指针返回结果数组的长度。
#include <stdio.h>
int main() {
int nums[] = {-4, -1, 0, 3, 10};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int returnSize;
int* result = sortedSquares(nums, numsSize, &returnSize);
printf("结果数组: ");
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
printf("\n");
free(result); // 释放动态分配的内存
return 0;
}本网站原创文章版权归何大锤的狂飙日记所有。发布者：何大锤，转转请注明出处：何大锤的博客
