镇海建设交通局网站首页,医院网站建设套餐方案,推广型网站建设公司,通用网站后台管理系统(php版)有序数组的平方
题目链接
题目#xff1a;给你一个按非递减顺序排序的整数数组 nums#xff0c;返回每个数字的平方组成的新数组#xff0c;要求也按非递减顺序排序。
//暴力
#includestdio.h
void sort(int *nums,int n){for(int i0;in;i)for(int ji1;j给你一个按非递减顺序排序的整数数组 nums返回每个数字的平方组成的新数组要求也按非递减顺序排序。
//暴力
#includestdio.h
void sort(int *nums,int n){for(int i0;in;i)for(int ji1;jn;j){if(nums[i]nums[j]){int tempnums[i];nums[i]nums[j];nums[j]temp;}}
}int main(){int nums[]{-4,-1,0,3,10};int nsizeof(nums)/sizeof(nums[0]);for(int i0;in;i)nums[i]nums[i]*nums[i];sort(nums,n);for(int i0;in;i)printf(%d ,nums[i]);
}
聪明方法双指针
数组其实是有序的只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端不可能是中间。此时可以考虑双指针分别指向头和尾。
并且此题没规定空间复杂度故可以新建一个数组。
//双指针
//学会这个思想的变化
#includestdio.h
int main(){int nums[]{-11,-2,3,4,5,6,7};int nsizeof(nums)/sizeof(nums[0]);int result[n];//构建一个新数组int kn-1;//作为新数组的索引//***由于原数组两边的平方比中间大并且大的要在新数组后面故初始值为n-1 for(int i0,jn-1;ij;){ //定义两个指向头和尾的索引;注意ij,因为最后还有一个元素要加进去 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 i0;in;i)printf(%d ,result[i]);
}
