如何将指定JSON结构转换的时间复杂度优化至O(n)？

输入JSON #

const i = {
  "38931": [{
      "userT": "z",
      "personId": 13424,
      "user": {
        "id": 38931,
        "email": "sample",
      },
    },
    {
      "userType": "z",
      "personId": 19999,
      "user": {
        "id": 38931,
        "email": "sample",
      },
    }
  ],
  "77777": [{
    "userT": "z",
    "personId": 55555,
    "user": {
      "id": 77777,
      "email": "sample",
    },
  }]
}

期望输出JSON #

{
  "38931": {
    "13424": {
      "userT": "z",
      "personId": 13424,
      "user": {
        "id": 38931,
        "email": "sample"
      }
    },
    "19999": {
      "userType": "z",
      "personId": 19999,
      "user": {
        "id": 38931,
        "email": "sample"
      }
    }
  },
  "77777": {
    "55555": {
      "userT": "z",
      "personId": 55555,
      "user": {
        "id": 77777,
        "email": "sample"
      }
    }
  }
}

原实现代码及问题 #

原代码通过多次reduce和flat完成转换，但最后一个reduce中的...acc[id]对象展开操作会导致时间复杂度升至O(n²)——因为每次展开都要遍历目标对象的已有属性。

const i = {
  "38931": [{
      "userT": "z",
      "personId": 13424,
      "user": {
        "id": 38931,
        "email": "sample",
      },
    },
    {
      "userType": "z",
      "personId": 19999,
      "user": {
        "id": 38931,
        "email": "sample",
      },
    }
  ],
  "77777": [{
    "userT": "z",
    "personId": 55555,
    "user": {
      "id": 77777,
      "email": "sample",
    },
  }]
}


const accList = (acc, id) => {
  acc.push(i[id]);
  return acc;
}
const accObject = (acc, [key, val]) => {
  const {
    user: {
      id
    }
  } = val;
  acc[id] = {
    ...acc[id],
    [key]: val
  };
  return acc;
}

const personas = Object.keys(i)
  .reduce(accList, [])
  .flat()
  .reduce((acc, obj) => {
    acc[obj.personId] = obj;
    return acc;
  }, {});

const result =
  Object
  .entries(personas)
  .reduce(accObject, {});

console.log('result', result);

优化方案：O(n)时间复杂度实现 #

直接遍历原对象的键值对，对每个数组元素直接构建目标层级结构，避免不必要的中间转换和对象展开操作，全程仅做线性遍历：

const i = {
  "38931": [{
      "userT": "z",
      "personId": 13424,
      "user": {
        "id": 38931,
        "email": "sample",
      },
    },
    {
      "userType": "z",
      "personId": 19999,
      "user": {
        "id": 38931,
        "email": "sample",
      },
    }
  ],
  "77777": [{
    "userT": "z",
    "personId": 55555,
    "user": {
      "id": 77777,
      "email": "sample",
    },
  }]
}

const result = {};

// 遍历原对象的每个用户ID对应的数组
for (const userId of Object.keys(i)) {
  // 初始化当前用户ID对应的对象（不存在则创建）
  result[userId] = result[userId] || {};
  // 遍历数组中的每个人员项
  for (const item of i[userId]) {
    // 直接将人员项以personId为键存入对应层级
    result[userId][item.personId] = item;
  }
}

console.log('result', result);

优化说明 #

• 时间复杂度为O(n)：外层遍历原对象的键，内层遍历每个键对应的数组元素，总操作次数等于所有元素的总数，无额外重复遍历。
• 空间复杂度更优：无需创建personas这类临时中间对象，直接在结果对象上构建结构。
• 逻辑更简洁：去掉了冗余的数组扁平化、多次reduce转换步骤，代码可读性更强。

内容的提问来源于stack exchange，提问作者EugenSunic