有序数组排序
题目描述
算法题解
思路1——双指针法
按照题目[额外要求]可以排除[暴力解法],分析题目条件可得数组是有序的(即递增),且题目示例中包含正数和负数,所以平方后数组中的最大值就在数组的[两端],即左边或者右边,不可能是中间,既然有双端的操作,我们可以尝试双指针法,具体流程如下:
1.定义两个指针i和j分别指向nums数组的起始和终止位置。
2.定义一个和nums 等长的[辅助数组] result綻义指针k指向result数组终止位置。
3.如果nums[i] * nums[i] < nums[j] * nums[j] 那么result[k--] = nums[j] * nums[j]。
4.如果nums[i] * nums[i] > nums[j] * nums[j] 那么result[k--] = nums[i] * nums[i]。
上机代码
#include <stdio.h>
#include <math.h>
int main(){
int nums[]={-4,-1,0,3,10};
int length=sizeof(nums)/sizeof(nums[0]);//记录数组长度
int result[length];//记录数组元素平方后进行排序后的结果
int k=length-1;
int a=0,b=length-1;
int c,d;
while(a<=b){
if(pow(nums[a],2)<pow(nums[b],2)){
result[k--]=pow(nums[b--],2);
}
else{
result[k--]=pow(nums[a++],2);
}
}
for(int i=0;i<length;i++){
printf("%d\n",result[i]);
}
return 0;
}