[977. Squares of a Sorted Array]

[(https://leetcode.cn/problems/squares-of-a-sorted-array/)

暴力解法

• 对数组中每个元素平方后再排序

• 代码如下：

  class Solution {
  public:
      vector<int> sortedSquares(vector<int>& nums) {
          for (int i = 0; i < nums.size(); i++) {
              nums[i] *= nums[i];
          }
          sort(nums.begin(), nums.end()); 
          return nums;
      }
  };
  

• 时间复杂度： O(n + nlogn)

  空间复杂度：O（1）

双指针

• 根据题意，数组内元素是按non-decreasing排列。因此，最大数必然要么在左要么在右，不可能在中间

• 故，我们设置 l = 0， r = nums.size() - 1 ，让i指向起始位置，而r指向最终位置，两边不断向中间移动

• 再者，我们创建一个与nums大小相同的新数组，让i指向数组的最终位置

• 若nums[ l ] * nums[ l ] < nums[ r ] * nums[ r ]，result[ i-- ] = nums[ r ] * nums[ r ]

  若nums[ l ] * nums[ l ] > nums[ r ] * nums[ r ]，result[ i-- ] = nums[ l ] * nums[ l ]

• 代码如下：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int i = nums.size() - 1;
        vector<int>result( i + 1 );
        for( int l = 0, r = nums.size() - 1; l <= r; )	//最后需处理一个元素，因此为l <= r
        {
            if( nums[l] * nums[l] < nums[r] * nums[r] )
            {
                result[i--] = nums[r] * nums[r];
                --r;
            }
            else
            {
                result[i--] = nums[l] * nums[l];
                ++l;
            }
        }
        return result;
    }
};

• 时间复杂度：O(n)

  空间复杂度：O(1)