Question

在 javascript 中合并两个不同的相关对象数组

2022-08-26

68

javascript loops time-complexity

我有两个对象数组（用户和存款）。

const users = [
    {
        _id: 1,
        username: 'tajmirul',
        email: '[email protected]',
    },
    {
        _id: 2,
        username: 'tajmirul2',
        email: '[email protected]',
    },
];

const deposits = [
    {
        _id: 1,
        userId: 1,
        amount: 250,
    },
    {
        _id: 2,
        userId: 1,
        amount: 500,
    },
];

我想计算每个用户的总存款并更新用户数组。像这样

// modified users array will look like this
[
    {
        _id: 1,
        username: 'tajmirul'
        deposit: 750,
    },
    {
        _id: 2,
        username: 'tajmirul2'
        deposit: 0,
    }
]

我试过了

users.forEach((user, index) => {
    deposits.forEach(deposit => {
        if (user._id === deposit.userId) {
            if (users[index].deposit) {
                users[index].deposit += deposit.amount;
            } else {
                users[index].deposit = deposit.amount;
            }
        }
    });
});

在这种情况下，时间复杂度为 O(m * n)。有什么方法可以降低时间复杂度吗？

Answer 1

您可以创建一个哈希映射，并按用户 ID 索引存款。

这将为您提供 O(m)

用户规模 = n ，存款规模 = m

之后，您可以迭代用户，这将是 O(n)

最后，时间复杂度将是 O(MAX(m,n))

const users = [
  {
    _id: 1,
    username: 'tajmirul',
    email: '[email protected]',
  },
  {
    _id: 2,
    username: 'tajmirul2',
    email: '[email protected]',
  },
];

const deposits = [
  {
    _id: 1,
    userId: 1,
    amount: 250,
  },
  {
    _id: 2,
    userId: 1,
    amount: 500,
  },
];


const depositsMap = new Map();

for (const deposit of deposits) { // O(m)
  if (depositsMap.has(deposit.userId)) {
    const prevDeposit = depositsMap.get(deposit.userId);
    depositsMap.set(deposit.userId, prevDeposit + deposit.amount);
  } else {
    depositsMap.set(deposit.userId, deposit.amount ?? 0);
  }
}

const aggregatedUsers = users.map(user => { // O(n)
  return {
    _id: user._id,
    username: user.username,
    deposit: depositsMap.get(user._id) ?? 0,
  };
});

console.log(aggregatedUsers);

Answer 2

const usersWithAmount = users.map((user) => {
  const { _id } = user;
  const depositsFiltered = deposits.filter(({ userId }) => userId === _id);
  if (depositsFiltered.length > 0) {
    return {
      ...user,
      deposit:
        (user?.deposit ?? 0) +
        depositsFiltered.reduce((acc, { amount }) => (acc + amount), 0),
    };
  }
  return { ...user, amount: 0 };
});

Answer 3

您可能首先 减少 存款至 {userId:total ，即 O(n)，
然后更新用户，即 O(m)：

const users = [
    {
        _id: 1,
        username: 'tajmirul',
        email: '[email protected]',
    },
    {
        _id: 2,
        username: 'tajmirul2',
        email: '[email protected]',
    },
];

const deposits = [
    {
        _id: 1,
        userId: 1,
        amount: 250,
    },
    {
        _id: 2,
        userId: 1,
        amount: 500,
    },
];

const userDeposits = deposits.reduce((a, {userId, amount}) => (a[userId] = (a[userId] || 0) + amount, a), {}) // O(n)

users.forEach(u => u.amount = userDeposits[u._id] || 0) // O(m)

console.log(users)

.as-console-wrapper {
  top: 0;
  max-height: none !important;
  }