有序数组的平方

记录过程题目链接理解题意给你一个递增的一维数组返回平方之后的升序数组输入 一维数组输出返回平方之后的升序数组边界条件题目没有给出但是应该要考虑数组为空的情况时间复杂度要O(n)举例验证nums [-4,-1,0,3,10]返回 [0,1,9,16,100]nums [-7,-3,2,3,11]返回 [4,9,9,49,121]暴力解法 我的第一个想法不是最优解哈正数无所谓对吧关键的是负数, 那么把正数和负数分开思路描述遍历传入的nums若nums[i]0 则加入到negative数组中去若是正数则加入到positive数组中去i指向negative的第一个元素j指向positive的第一个元素比较两个数的绝对值大小小的直接加入到res中去对应的指针往后移动classSolution{publicint[]sortedSquares(int[]nums){// 1. 遍历传入的nums拆分 negative 和 positivejava.util.ListIntegernegativenewjava.util.ArrayList();java.util.ListIntegerpositivenewjava.util.ArrayList();for(intnum:nums){if(num0){negative.add(num);}else{positive.add(num);}}// 结果数组int[]resnewint[nums.length];intindex0;// 2. i指向negative的最后一个元素因为负数绝对值越小越靠近0也就是越靠后// j指向positive的第一个元素intinegative.size()-1;intj0;// 3. 比较两个数的绝对值大小小的直接加入到res中去while(i0jpositive.size()){intabsNegMath.abs(negative.get(i));intpospositive.get(j);if(absNegpos){res[index]absNeg*absNeg;i--;// 对应的指针移动}else{res[index]pos*pos;j;// 对应的指针移动}}// 处理剩余的元素// 如果 negative 还有剩余while(i0){intvalnegative.get(i);res[index]val*val;i--;}// 如果 positive 还有剩余while(jpositive.size()){intvalpositive.get(j);res[index]val*val;j;}returnres;}}N是nums的长度时间复杂度O(N)空间复杂度O(N)优化思路暴力解法的空间复杂度太高了注意题目中的条件是升序如果想要一次性就确定平方之后的数字在最终结果数组中的位置那么我就需要保证这个数字平方之后是最大的当前区间当前区间内能产生最大值的可能性只会在两个极端里面即要么负数很小要么正数很大感不感觉有点类似于双指针呢ok思路如下start指针指向nums的第一个元素end指针指向nums的第二个元素随后比较start与end指向的元素的平方之后的结果将最大的max直接扔到res中去倒着存储随后startend中的一个移动classSolution{publicint[]sortedSquares(int[]nums){intnnums.length;int[]resnewint[n];intp_nnums.length-1;intstart0;intendn-1;while(startend){intsquare_startnums[start]*nums[start];intsquare_endnums[end]*nums[end];if(square_startsquare_end){res[p_n--]square_start;start;}else{res[p_n--]square_end;end--;}}returnres;}}