有序数组的平方
第一种，先平方后排序
#include <stdio.h>
#include <stdlib.h>
// 比较函数，用于快速排序
int compare(const void* a, const void* b) {
int A = *((int*)a);
int B = *((int*)b);
if (A < B) {
return -1;
}
else if (A > B) {
return 1;
}
else {
return 0;
}
}
int* sortedSquares(int* A, int ASize, int* returnSize) {
// 对每个元素进行平方
for (int i = 0; i < ASize; i++) {
A[i] *= A[i];
}
// 对平方后的数组进行快速排序
qsort(A, ASize, sizeof(int), compare);
// 设置返回数组的大小
*returnSize = ASize;
return A;
}
int main() {
int A[] = { -4, -1, 0, 3, 10 }; // 示例输入数组
int size = sizeof(A) / sizeof(A[0]); // 数组的大小
int returnSize; // 返回的数组大小
int* result = sortedSquares(A, size, &returnSize); // 调用排序函数
// 输出排序后的数组
printf("Sorted Squares: ");
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
printf("\n");
return 0;
}
这个时间复杂度是 O(n + nlogn)
第二种方法
双指针法
数组其实是有序的， 只不过负数平方之后可能成为最大数了。
那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
此时可以考虑双指针法了，i指向起始位置，j指向终止位置。
定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。
此时的时间复杂度为O(n)
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
int* ans = malloc(sizeof(int) * numsSize);
*returnSize = numsSize;
for (int i = 0, j = numsSize - 1, pos = numsSize - 1; i <= j;) {
if (nums[i] * nums[i] > nums[j] * nums[j]) {
ans[pos] = nums[i] * nums[i];
++i;
}
else {
ans[pos] = nums[j] * nums[j];
--j;
}
--pos;
}
return ans;
}
归并排序思想，官方题解
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
int negative = -1;
for (int i = 0; i < numsSize; ++i) {
if (nums[i] < 0) {
negative = i;
}
else {
break;
}
}//找到负数与非负数的边界
int* ans = malloc(sizeof(int) * numsSize);
*returnSize = 0;//初始化
int i = negative, j = negative + 1;
//如果我们能够找到数组 nums 中负数与非负数的分界线，那么就可以用类似「归并排序」的方法了。
// 具体地，我们设 neg 为数组 nums 中负数与非负数的分界线，
// 也就是说，nums[0] 到 nums[neg] 均为负数，而 nums[neg+1] 到 nums[n−1] 均为非负数。
// 当我们将数组 nums 中的数平方后，那么 nums[0] 到 nums[neg] 单调递减，nums[neg+1] 到 nums[n−1] 单调递增。
//由于我们得到了两个已经有序的子数组，因此就可以使用归并的方法进行排序了。
// 具体地，使用两个指针分别指向位置 neg 和 neg + 1，每次比较两个指针对应的数，选择较小的那个放入答案并移动指针。
// 当某一指针移至边界时，将另一指针还未遍历到的数依次放入答案。
while (i >= 0 || j < numsSize) {
if (i < 0) {
// 如果 i 小于 0，则说明已经遍历完了 nums 数组中的负数部分
// 将 nums[j] 的平方放入 ans 数组，并将 j 指针向后移动一位
ans[(*returnSize)++] = nums[j] * nums[j];
++j;
}
else if (j == numsSize) {
// 如果 j 等于 numsSize，则说明已经遍历完了 nums 数组中的非负数部分
// 将 nums[i] 的平方放入 ans 数组，并将 i 指针向前移动一位
ans[(*returnSize)++] = nums[i] * nums[i];
--i;
}
else if (nums[i] * nums[i] < nums[j] * nums[j]) {
// 如果 nums[i] 的平方小于 nums[j] 的平方，则将 nums[i] 的平方放入 ans 数组
// 并将 i 指针向前移动一位
ans[(*returnSize)++] = nums[i] * nums[i];
--i;
}
else {
// 如果 nums[i] 的平方大于等于 nums[j] 的平方，则将 nums[j] 的平方放入 ans 数组
// 并将 j 指针向后移动一位
ans[(*returnSize)++] = nums[j] * nums[j];
++j;
}
}
return ans;
}