如何高效遍历数组的问题

Question

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

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

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

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

Answer 1

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)，但不见得实际执行时间就大，具体问题具体分析。

Answer 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);