LC977. 有序数组的平方 C语言

LC977问题要求对一个有序数组进行平方，并返回一个新的有序数组。以下是一个详细的C语言解决方案：

问题描述

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

思路

因为输入数组是有序的，所以负数平方后的结果可能会变大，而正数平方后的结果依然是有序的。我们可以利用双指针方法，从数组两端向中间移动，比较平方后的值，将较大的值放入结果数组的末尾。

代码实现

以下是完整的C语言代码实现：

c
复制代码
#include <stdio.h>
#include <stdlib.h>

// 函数声明
int* sortedSquares(int* nums, int numsSize, int* returnSize);

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("Sorted squares: ");
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    // 释放动态分配的内存
    free(result);
    
    return 0;
}

int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    int* result = (int*)malloc(numsSize * sizeof(int));
    *returnSize = numsSize;
    
    int left = 0;
    int right = numsSize - 1;
    int pos = numsSize - 1;
    
    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--;
    }
    
    return result;
}

代码解析

1. 函数声明和主函数：

   • sortedSquares函数用于处理问题逻辑。
   • main函数中创建一个示例数组，并调用sortedSquares函数，最后打印结果并释放内存。

2. sortedSquares函数：

   • 动态分配一个数组result用于存储结果。
   • 使用两个指针left和right分别指向数组的两端。
   • 使用while循环遍历数组，并将平方后的较大值放入结果数组的末尾。
   • 根据平方值的比较结果，移动相应的指针。

3. 内存管理：

   • 动态分配的内存在主函数中使用后需要释放，防止内存泄漏。

关键点

• 双指针技巧：利用有序数组的性质，从两端向中间移动，比较平方后的值。
• 动态内存分配：确保返回的结果数组在函数外部可以访问。

通过上述方法，可以高效地解决LC977问题，确保时间复杂度为O(n)。