Después de tener un desafío de codificación largo y difícil, hubo un problema que me molestó. Lo pensé por un tiempo adecuado pero no pude encontrar la manera de solucionarlo. Aquí, estoy proporcionando un problema y un ejemplo a continuación.
v es una matriz y q es un comando que hace cosas diferentes según su elemento anidado.
si el primer elemento de la matriz anidada es 1 => el segundo y tercer elemento de la matriz anidada se convierte en el índice y devuelve sum[second:third+1] (como puede ver, es inclusivo)
si el primer elemento de la matriz anidada es 2 => el elemento del segundo índice se convierte en el tercero. igual que v[second] = third
Con un ejemplo proporcionado, va como
[1,2,4] => el primer elemento es 1 . debería devolver la suma de v[2] a v[4] (inclusive) => 12.[2,3,8] => el primer elemento es 2 . cambia v[3] a 8 . (ahora v es [1,2,3,8,5] )[1,2,4] => el primer elemento es 1 . debería devolver la suma de v[2] a v[4] (inclusive) => 16, ya que el tercer índice se ha cambiado desde el comando anterior.Así que la respuesta final es [12, 16]
El siguiente código es cómo resolví, sin embargo, esta es una complejidad O (n ** 2). Me pregunto cómo puedo reducir la complejidad del tiempo en este caso.
Intenté hacer un objeto hash, pero no funcionó. No puedo pensar en una buena manera de hacer un caché en este caso.
function solution(v, q) { let answer = []; for (let i = 0; i < q.length; i++) { let [a, b, c] = q[i]; if (a === 1) { let sum = 0; for (let i = b; i <= c; i++) { sum += v[i]; } answer.push(sum); } else if (a === 2) { v[b] = c; } } return answer; }Este tipo de problema generalmente se puede resolver de manera más eficiente con un árbol de Fenwick.
Aquí hay una implementación:
class BinaryIndexedTree extends Array { constructor(length) { super(length + 1); this.fill(0); } add(i, delta) { i++; // make index 1-based while (i < this.length) { this[i] += delta; i += i & -i; // add least significant bit } } sumUntil(i) { i++; // make index 1-based let sum = 0; while (i) { sum += this[i]; i -= i & -i; } return sum; } } function solution(values, queries) { const tree = new BinaryIndexedTree(values.length); values.forEach((value, i) => tree.add(i, value)); const answer = []; for (const [a, b, c] of queries) { if (a === 1) { answer.push(tree.sumUntil(c) - tree.sumUntil(b - 1)); } else { tree.add(b, c - values[b]); values[b] = c; } } return answer; } let answer = solution([1,2,3,4,5], [[1,2,4], [2,3,8], [1,2,4]]); console.log(answer); La complejidad temporal de ejecutar tree.add o tree.sumUntil una vez es O(log𝑛), donde 𝑛 es el tamaño de los valores de entrada ( values.length ). Entonces, esta es también la complejidad del tiempo de ejecutar una consulta.
values cuesta O(𝑛log𝑛), ya que en realidad cada valor en la entrada actúa como una consulta que actualiza un valor de 0 al valor real.queries.length es el número de consultas (consultas.longitud)Entonces, en total, tenemos una complejidad de tiempo de O(𝑛 + 𝑛log𝑛 + 𝑚log𝑛) = O((𝑚+𝑛)log𝑛)
Para obtener más información sobre los árboles Fenwick, consulte BIT: ¿Cuál es la intuición detrás de un árbol indexado binario y cómo se pensó?