当前位置：首页 > article >正文

代码随想录--977有序数组的平方

article 2025/2/13 2:32:23

977 有序数组的平方

题目：

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

示例 1：

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

示例 2：

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

提示：

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

考点：

1、数组内元素排序

解法1：

暴力求解：数组内元素平方得到新数组，对新数组元素重新排序（依次从小到大），选择快排。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#include <stdio.h>
#include <stdlib.h>
//比较两个整数，a是void*类型指针，强制类型转换(int *) a,需要比较数值大小，即(*(int*)a）解引用a，得到a指向的整数值
int cmp(const void* a, const void* b) { return (*(int*)a - *(int*)b); }

int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    //遍历原数组元素
    for (int i = 0; i < numsSize; i++) {
        nums[i] = nums[i] * nums[i]; // 元素平方
    }
    // 排序
    qsort(nums, numsSize, sizeof(int), cmp);
    //返回数组大小
    *returnSize = numsSize;
    return nums;
}

解法2：

双指针法：双指针从相反方向开始移动，i依次从左至右，j依次从右至左；比较i、j指向的数组元素平方值大小，较大者存放于新数组，新数组依次从右至左遍历。更新i、j数值。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
// 双指针法
// i依次从左至右遍历,j依次从右至左遍历
// 比较数组元素大小,寻找相对较大的元素
// 将较大元素依次从右至左存放于新数组

int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    // 创建两个指针
    int j = numsSize - 1;
    int i = 0;
    // 创建新的数据
    int* result = (int*)malloc(sizeof(int) * numsSize);

    // 遍历新的数组
    for (int index = numsSize - 1; index >= 0; index--) {
        // 存放原数组元素平方
        int left = nums[i] * nums[i];
        // 存放原数组元素平方
        int right = nums[j] * nums[j];
        // 比较左右指针数组元素大小
        if (left > right) {
            // 左指针数组元素存放于新数组
            result[index] = left;
            // 更新指针
            i++;
        } else {
            result[index] = right;
            j--;
        }
    }
    // 设置返回的数组大小
    *returnSize = numsSize;
    return result;
}