Number of elements with lower index equal to some element, for all items on an array
-
05-11-2019 - |
Pergunta
Let $A$ be an array of size $n$, and $f(i, r, a_r)$ be the number of indices $k$ such that $a_k$ = $a_r$ and $i \le k \le r$.
Example to clarify:
Imagine the array: $[1, 2, 3, 2, 2, 3, 4, 5]$. $f(0, 3, a_3)$, for example, would be equal to 2, because there are 2 elements in the array that appear before $a_3$ (which is 2) and are equal to it.
I've heard one of my colleagues talk about using a Fenwick Tree, but I don't see how that could be done.
I'd like to know if there´s a way to solve this problem in $O(n)$. By solving it I mean finding every value of $f$ for a fixed $i = 0$ and $r = [0, n-1]$
Space isn't really a problem, as long as it's polynomial.
Nenhuma solução correta
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange