福建整站优化广告资源对接平台

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;
}