有序数组的平方。题意是给一个非降序的数组,请输出一个新数组,包含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 };