著作权归领扣网络所有.商业转载请联系官方授权,非商业转载请注明出处.
最容易想到的方法就是先平方再排序,这样时间复杂度O(nlogn)
但是这题有A的非递减特性可以利用,非负数的平方还是一个非递减顺序,负数的平方是一个非递增序列,将其逆序就是非递减序列了.于是可以先找到非负数和负数的分界线,然后使用双指针依次比较非负数和负数平方后的数值,填入较小的数值,指针后移.
然后注意双指针的边界条件即可.
时间复杂度是O(n),我使用一个临时数组存储了序列平方后的数值,空间复杂度O(n).因为个人觉得如果每次都将数平方比较的话,乘法运算耗时较长,所以使用了临时数组.
给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序.
--left;