[LeetCode] 977. Squares of a Sorted Array

有序数组的平方。题意是给一个非降序的数组,请输出一个新数组,包含input里面每个数字的平方。例子,

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]

思路是two pointer夹逼。创建一个跟input同样长度的数组。因为input里面存在负数,而且很有可能存在一个绝对值非常大的负数,导致其平方值最大,所以需要two pointer左右指针比较哪个数字的绝对值大。细节实现参见代码。

时间O(n)

空间O(n) - output

 1 /**
 2  * @param {number[]} A
 3  * @return {number[]}
 4  */
 5 var sortedSquares = function (A) {
 6     let n = A.length;
 7     let res = [n];
 8     let i = 0;
 9     let j = n - 1;
10     for (let p = n - 1; p >= 0; p--) {
11         if (Math.abs(A[i]) > Math.abs(A[j])) {
12             res[p] = A[i] * A[i];
13             i++;
14         } else {
15             res[p] = A[j] * A[j];
16             j--;
17         }
18     }
19     return res;
20 };

 

上一篇:[Leetcode]977. Squares of a Sorted Array


下一篇:Leetcode刷题2-977. 有序数组的平方(C++)