如何高效遍历数组的问题

国家战略忽悠局
  • 388

两个长度为500的数组,数组的每一项都是一个对象:

//数组1
[
  {
    id: 123,
    ...
  }
  ...
]
//数组2
[
  {
    itemId: 123,
    value: 1,
    ...
  }
  ...
]

数组1每一项的id和数组2某一项的itemId相等,数组1的项中没有value,需要把数组2每一项的value赋给数组1中id与itemId相等的项。请问怎么遍历最快?

回复
阅读 379
2 个回答

itemId 是唯一的吗?

如果是可以考虑先把数组二变为以 itemId 为 Key 的字典结构,然后遍历数组一时直接从这个字典里取值就可以了。

// 伪代码,看大致思路
let temp = {};
arr2.forEach(k => { temp[k.itemId] = k.value; });
arr1.forEach(e => { e.value = temp[e.id]; });

这样做时间复杂度是 O(n) (实际是 T(2n+1),但去掉常数项就是 O(n))。

应该没有可以做到 O(1) 的算法……吧…… 😂

P.S. 单纯以时间复杂度衡量快慢其实没啥意义,你就是双重 for 嵌套循环取值,时间复杂度时 O(n^2),但不见得实际执行时间就大,具体问题具体分析。

两次循环

const setArrayTo=(arr1, arr2)=>{
 let arr2Map = arr2.reduce((acc,cur)=>(acc[cur.id]=cur,acc),{});
 arr1.forEach(item=>item.value||=arr2Map[item.itemId].value);
 }
let arr1 = [{id:123,value:''},{id:265,value:4654}];
let arr2 = [{itemId:123,value:123},{itemId:265,value:4654}]

setArrayTo(arr1, arr2);
console.log(arr1,arr2);

image.png

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
你知道吗?

宣传栏