有序數組的平方

題目鏈接

題目：給你一個按非遞減順序排序的整數數組 nums，返回每個數字的平方組成的新數組，要求也按非遞減順序排序。

//暴力 
#include<stdio.h>
void sort(int *nums,int n){for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){if(nums[i]>nums[j]){int temp=nums[i];nums[i]=nums[j];nums[j]=temp;}}
}int main(){int nums[]={-4,-1,0,3,10};int n=sizeof(nums)/sizeof(nums[0]);for(int i=0;i<n;i++)nums[i]=nums[i]*nums[i];sort(nums,n);for(int i=0;i<n;i++)printf("%d ",nums[i]);
} 

聰明方法：雙指針

數組其實是有序的，只不過負數平方之后可能成為最大數了。那么數組平方的最大值就在數組的兩端，不可能是中間。此時可以考慮雙指針，分別指向頭和尾。

并且此題沒規定空間復雜度，故可以新建一個數組。

//雙指針
//學會這個思想的變化
#include<stdio.h>
int main(){int nums[]={-11,-2,3,4,5,6,7};int n=sizeof(nums)/sizeof(nums[0]);int result[n];//構建一個新數組int k=n-1;//作為新數組的索引//***由于原數組兩邊的平方比中間大，并且大的要在新數組后面，故初始值為n-1 for(int i=0,j=n-1;i<=j;){ //定義兩個指向頭和尾的索引;注意：i<=j,因為最后還有一個元素要加進去 if(nums[i]*nums[i]<nums[j]*nums[j]){result[k--]=nums[j]*nums[j];j--;} else{result[k--]=nums[i]*nums[i];i++;}}for(int i=0;i<n;i++)printf("%d ",result[i]);
}