学习---3

有序数组的排序一、暴力解法思路遍历数组对每个数组元素进行平方再用sort排序。时间复杂度O(nlog n)二、双指针解法思路如果有序数组中有负数那么这个负数平方之后就有可能比正数的平方大所以平方后最大的元素一定再数组的两边而不是中间。所以用两个指针一个指向第一个元素一个指向最后一个元素比较这两个指针所指的元素平方后哪个更大再用一个数组来存放更大的数然后指针移动。代码实现int arr[6]{-3,-2,-1,0,1,2}; int res[6]{0}; //用于存放比较好后的元素 int ksizeof(arr)/sizeof(arr[0])-1; //记录存放res数组的位置 for(int i0,jsizeof(arr)/sizeof(arr[0])-1;ij;){ ifarr[i]*arr[i]arr[j]*arr[j]){ res[k--]arr[i]*arr[i]; i; }else{ res[k--]arr[j]*arr[j]; j--; } } //返回res数组时间复杂度为O(N);(本文章是本人学完后进行整理加入了自己的理解仅供参考有不正确的地方欢迎指出)