977 有序數(shù)組的平方

題目：

給你一個(gè)按 非遞減順序 排序的整數(shù)數(shù)組 nums，返回 每個(gè)數(shù)字的平方 組成的新數(shù)組，要求也按 非遞減順序 排序。

示例 1：

輸入：nums = [-4,-1,0,3,10]
輸出：[0,1,9,16,100]
解釋：平方后，數(shù)組變?yōu)?[16,1,0,9,100]
排序后，數(shù)組變?yōu)?[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 已按 非遞減順序 排序

考點(diǎn)：

1、數(shù)組內(nèi)元素排序

解法1：

暴力求解：數(shù)組內(nèi)元素平方得到新數(shù)組，對(duì)新數(shù)組元素重新排序（依次從小到大），選擇快排。

/*** Note: The returned array must be malloced, assume caller calls free().*/
#include <stdio.h>
#include <stdlib.h>
//比較兩個(gè)整數(shù)，a是void*類型指針，強(qiáng)制類型轉(zhuǎn)換(int *) a,需要比較數(shù)值大小，即(*(int*)a）解引用a，得到a指向的整數(shù)值
int cmp(const void* a, const void* b) { return (*(int*)a - *(int*)b); }int* sortedSquares(int* nums, int numsSize, int* returnSize) {//遍歷原數(shù)組元素for (int i = 0; i < numsSize; i++) {nums[i] = nums[i] * nums[i]; // 元素平方}// 排序qsort(nums, numsSize, sizeof(int), cmp);//返回?cái)?shù)組大小*returnSize = numsSize;return nums;
}

解法2：

雙指針?lè)?#xff1a;雙指針從相反方向開(kāi)始移動(dòng)，i依次從左至右，j依次從右至左；比較i、j指向的數(shù)組元素平方值大小，較大者存放于新數(shù)組，新數(shù)組依次從右至左遍歷。更新i、j數(shù)值。

/*** Note: The returned array must be malloced, assume caller calls free().*/
// 雙指針?lè)?/span>
// i依次從左至右遍歷,j依次從右至左遍歷
// 比較數(shù)組元素大小,尋找相對(duì)較大的元素
// 將較大元素依次從右至左存放于新數(shù)組int* sortedSquares(int* nums, int numsSize, int* returnSize) {// 創(chuàng)建兩個(gè)指針int j = numsSize - 1;int i = 0;// 創(chuàng)建新的數(shù)據(jù)int* result = (int*)malloc(sizeof(int) * numsSize);// 遍歷新的數(shù)組for (int index = numsSize - 1; index >= 0; index--) {// 存放原數(shù)組元素平方int left = nums[i] * nums[i];// 存放原數(shù)組元素平方int right = nums[j] * nums[j];// 比較左右指針數(shù)組元素大小if (left > right) {// 左指針數(shù)組元素存放于新數(shù)組result[index] = left;// 更新指針i++;} else {result[index] = right;j--;}}// 設(shè)置返回的數(shù)組大小*returnSize = numsSize;return result;
}