javascript - 针对给定问题的替代和优化解决方案

Question

这是我的面试题，我能解决，但是面试官留下了一张纸条，说这不是优化的代码，我无法在优化的解决方案中解决它，任何人都可以提供帮助。

问题:给定一个数组array1，按照格式重新排列数组

1. 所有负数及其绝对数首先插入数组(已排序)。
2. 并且所有剩余的项目应该连接到新数组(已排序)

//input 
var array = [8,7,0,6,4,-9,-7,2,-1,3,5,1,10];
//output
var array2 = [-7,7,-1,1,-9,0,2,3,4,5,6,8,10];

我的代码:

function sort(arr){  
  var arrange = arr.sort((a, b)=>{ return a-b});
  var array1=[];
  for(let i=0; i<arrange.length; i++){
    let firstItem = Math.abs(arrange[i]);
    for(let j=i+1; j<arrange.length; j++){
       if(firstItem === Math.abs(arrange[j])){
         array1.push(arrange[i], arrange[j])       
       }
   }
  }
  arrange = arrange.filter((item, i)=>{
     return array1.indexOf(item) === -1
  })
 return [...array1, ...arrange]
} 


console.log(sort(array));

JSBIN

也请大家指点，我的做法有什么问题。

注:我写的代码像o(n^2)，他要一个O(log n)，他的意思是，不用嵌套的for循环，我们就可以解决。我们可以吗？

Answer 1

这个解决方案不是优化的，因为如果我们忽略一些循环，比如排序和过滤的复杂性，会消耗处理时间。它具有 O(n^2) 复杂度。这意味着如果元素数量增加，则需要更多时间。

在这类问题中，尽可能忽略嵌套循环。