Tengo dos matrices de objetos (usuarios y depósitos).
const users = [ { _id: 1, username: 'tajmirul', email: 'tajmirul@gmail.com', }, { _id: 2, username: 'tajmirul2', email: 'tajmirul2@gmail.com', }, ]; const deposits = [ { _id: 1, userId: 1, amount: 250, }, { _id: 2, userId: 1, amount: 500, }, ];Quiero calcular el depósito total para cada usuario y actualizar la matriz de usuarios. como esto
// modified users array will look like this [ { _id: 1, username: 'tajmirul' deposit: 750, }, { _id: 2, username: 'tajmirul2' deposit: 0, } ]probé esto
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; } } }); });En este caso, la complejidad temporal es O(m * n). ¿Hay alguna forma de reducir la complejidad del tiempo?
Puede crear un mapa hash e indexar depósitos por ID de usuario.
Esto te da O(m)
Tamaño de Usuarios = n , Tamaño de Depósitos = m
Después de eso, puede iterar sobre los usuarios y eso sería O (n)
Al final, la complejidad del tiempo será O(MAX(m,n))
const users = [ { _id: 1, username: 'tajmirul', email: 'tajmirul@gmail.com', }, { _id: 2, username: 'tajmirul2', email: 'tajmirul2@gmail.com', }, ]; 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);Primero puede reduce los depósitos a {userId:total} , que es O(n),
luego actualice los usuarios que es O (m):
const users = [ { _id: 1, username: 'tajmirul', email: 'tajmirul@gmail.com', }, { _id: 2, username: 'tajmirul2', email: 'tajmirul2@gmail.com', }, ]; 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; }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 }; });