禁忌网站,安徽省建设干校网站,手机网站模板使用方法,火车头wordpress模块977 有序数组的平方
题目#xff1a;
给你一个按 非递减顺序 排序的整数数组 nums#xff0c;返回 每个数字的平方 组成的新数组#xff0c;要求也按 非递减顺序 排序。
示例 1#xff1a;
输入#xff1a;nums [-4,-1,0,3,10]
输出#xff1a;[0,1,9,16,100]
解释
给你一个按 非递减顺序 排序的整数数组 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] 104nums 已按 非递减顺序 排序
考点
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;
}
