数组合并优化

背景

需要将 10万条数据中 1万条的数据替换掉

其中 id 是一一对应的

// 原始数据 10w
const originalData = [
    {
        id: 1,
        name: 'cocos',
        age: 21
    },
    {
        id: 2,
        name: 'jiji',
        age: 26
    },
    ...
]

// 需要替换的数据 1w
const newData = [
    {
        id: 1,
        name: 'cocos',
        age: 28
    },
    {
        id: 2,
        name: 'jiji',
        age: 42
    },
    ...
]

简单实现

for (let i = 0; i < originalData.length; i++) {
    for (let j = 0; j < newData.length; i++) {
        if (originalData[i].id === newData[j].id) {
            originalData[i].age = newData[j].age
        }
    }
}

时间复杂度：O(n * n) -> 10w * 1w

空间复杂度：O(1)

优化实现

// 将数组 转 对象
const arrToObj = (arr: any[], key, type = 'arr') => {
  const obj = {}
  for (let i = 0; i < arr.length; i++) {
    const keyName = arr[i][key]
    if (!(keyName in obj)) {
      obj[keyName] = []
    }
    if (type === 'obj') {
      obj[keyName] = arr[i]
    } else {
      obj[keyName].push(arr[i])
    }
  }
  return obj
}

const newOriginalData = arrToObj(originalData, 'id') // 10w 次
for (let i = 0; i < newData.length; i++) {
    newOriginalData[newData[i].id].age = newData[i].age // 1w 次
}

const result = Object.values(newOriginalData) // 10w 次

时间复杂度：O(n) -> 10w + 10w + 1w

空间复杂度：O(n)

总结

以空间换时间