首页 > itarticle > 2019-03-23-squares of a sorted array

2019-03-23-squares of a sorted array

admin 11月 12, 2020 0

题目，977. Squares of a Sorted Array

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:
Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 2:
Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

解析

一个有正数和负数的升序数组，返回每个数的平方，按照升序排列.

直接每个数求平方，然后数组排序
空间复杂度O(n),时间复杂度nlog(n).
map时间复杂度是O(n), 排序的复杂度是n*log(n)

var sortedSquares = function (A) {
	A = A.map(x => x * x);
	A.sort((a, b) => a - b);

	return A;
};

时间复杂度O(n)

var sortedSquares = function (A) {
  let i = 0, j = A.length - 1
  let ans = [];
  while (i <= j) {
    if (Math.abs(A[i]) < Math.abs(A[j])) {
      ans.push(Math.abs(A[j]));
      j--;
    } else {
      ans.push(Math.abs(A[i]));
      i++;
    }
  }
  let res = []
  for (let i = ans.length - 1; i >= 0; i--) res.push(ans[i] * ans[i]);
  return res;
};