有序数组的平方

难度简单387
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
如
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

  1. 我的思路：把数组里的值切片提取平方后，再进行排序
  2. class Solution(object):
  3.     def sortedSquares(self, nums):
  4.         """
  5.         :type nums: List[int]
  6.         :rtype: List[int]
  7.         """
  8.         return sorted[num*num num for num in nums]
  9.  展开上面的式子：
  10.         list = []
  11.         for num in nums:
  12.             num=num*num
  13.             list.append(num)
  14.         return sorted(list)

大佬思路：
数组原本是有序的, 只是在平方之后就变得无序了, 根本原因就是负数平方之后可能成为最大数了, 那么数组平方的最大值就在数组的两端, 不是最左边就是最右边, 不可能是中间.
这样我们就能确定了平方后最大值的位置, 所以用双指针指向数组的两端, 必定能找到平方后的最大值, 将其放到新数组末尾, 之后不断向中间移动, 通过比较两个指针平方后的大小, 就能不断地将当前的最大值放入数组的尾部, 直到两个指针相遇为止.
这种一种比较简单的双指针实现方式, 另外一种稍微麻烦一点的方式就是 先找到负值和正值的分界点, 相当于找到了平方后的最小值, 然后向两边不断进行遍历, 不过这种方法还多了一层循环来找分界点, 这种思想也要了解一下, 对于之后的题目还是挺有用的.

既然数组原来是按从小到大的顺序排列的。那平方之后要么最之前最小的变成最大，要么，原本最大的变成最大。y=x^2,如下图，所以就可以
4610b912c8fcc3ce042efd0b9045d688d43f201f.jpg

  1. class Solution:
  2.     def sortedSquares(self, nums):
  3.         n = len(nums)
  4.         ans = [0]*n
  5.         #从两端开始遍历，找到平方最大的元素放到数组末尾
  6.         i,j,pos=0,n - 1, n-1
  7.         while i <=j:
  8.             if nums[i] * nums[i] > nums[j]*nums[j]:
  9.                 ans[pos]=nums[i]*nums[i]
  10.                   i+=1
  11.             else:
  12.                 ans[pos]= nums[j]*nums[j]
  13.                 j-=1
  14.             pos  -=1
  15.         return ans