1. Sort the squares of ordered arrays

Given the ordered array [-4,-1,0,3,10], sort the array by square each value. The time complexity is O(n).

Train of thought
  1. Because we know the order, the square part of the complex number is decreasing monotonically. The positive part increases separately.
  2. Split into an array of positive and complex numbers, and then invert and square the negative numbers.
  3. Each array is given a pointer ab, starting with the first one. When the value of a is less than the value of b, add the value of A to the result array, a+=1;

Similarly, if the value of b is smaller, add the value of b, b+=1; Whichever way you like, it doesn’t matter. When both arrays are iterated (I have one iterated and add the remaining one to the array) 4. The first function uses binary lookup to find the positive and negative boundaries. Binary search can be seen in my other introduction

function searSplit(arr) { let leftIndex = 0; let rightIndex = arr.length - 1; let middle; while (leftIndex <= rightIndex) { middle = Math.floor((leftIndex + rightIndex) / 2); if(leftIndex === rightIndex){ return arr[middle] ===0 ? middle : LeftIndex} if(0 > arr[middle]){leftIndex = middle + 1}else{rightIndex = middle}}} function fn(arr) { If (arr[0] < 0) {let splitIndex; splitIndex = searSplit(arr); let leftArr = arr.slice(0, splitIndex); leftArr.sort((a,b) => b-a); leftArr = leftArr.map(item => item * item); let rightArr = arr.slice(splitIndex); rightArr = rightArr.map(item => item * item); let leftIndex = 0; let rightIndex = 0; let result = [] while (leftIndex <= leftArr.length - 1 || rightIndex <= rightArr.length - 1) { let leftVal = leftArr[leftIndex]; let rightVal = rightArr[rightIndex]; if(leftIndex>=leftArr.length){ return result.concat(rightArr.slice(rightIndex)) } if(rightIndex>=rightArr.length){ console.log(leftIndex) return result.concat(leftArr.slice(leftIndex)) } if(leftVal < rightVal){ leftIndex ++ result.push(leftVal) }else if(leftVal > rightVal ) { rightIndex ++; result.push(rightVal); }else{ leftIndex ++; result.push(leftVal); } } return result; } return arr.map(item => item * item); } console.log(fn([-4, -1, 0, 3, 10]))Copy the code