Como você encontra todos os inteiros em uma matriz classificada de tamanho n que aparecem n / k vezes?

Question

Eu tento encontrar a solução para este problema: Como você encontra todos os inteiros em uma matriz classificada de tamanho n que aparecem n / k vezes em menos do que o (klogn) tempo?

Eu só poderia encontrar Esta pergunta , onde a solução O (Klogn) foi fornecida.

Answer 1

Vamos começar com o caso $ k= 2 $ e suponha que o algoritmo seja baseado em comparação.

Eu afirmo que qualquer algoritmo que encontra mesmo um único elemento que aparece $ n / 2 $ vezes deve saber um índice $ i $ tal que $ a [i + 1]= a [i + n / 2] $ . De fato, suponha que este não seja o caso, e deixe-nos assumir a simplicidade que as entradas de $ a $ são números reais. Vamos dizer que o algoritmo conhecia os seguintes valores: $$ A [I_1]=CDOts= A [J_1] É consistente com o conhecimento do algoritmo de que $ a [I_1-1] e assim por diante e com um pouco esforço podemos providenciar que não há elemento aparecendo $ n / 2 $ vezes.

Considere agora a $ n / 2 + 1 $ matrizes do seguinte formulário: há uma execução de $ n / 2 $ muitas $ 0 $ s a partir de alguma posição $ j \ in \ {1, \ lDOTS, n / 2 + 1} $ , e o restante dos elementos são exclusivos. Em cada um desses array, há uma escolha única para o índice $ i $ mencionado acima. Assim, a árvore de decisão que representa o algoritmo tem pelo menos $ n / 2 + 1 $ folhas, e por isso deve ter profundidade $ \ Ômega (\ log n) $ .

---

.

No caso geral, o algoritmo deve conhecer um índice $ i $ tal que $ a [i + 1]= A [i + n / k] $ para cada elemento que é de saída. Podemos dividir a matriz em $ k / 2 $ partes de tamanho $ 2n / k $ e considere $ (n / k + 1) ^ k $ exemplos como antes, onde a $ R $ th elemento Aparecendo $ n / k $ vezes é na parte $ R $ th. Isso dá um limite inferior de $ \ ômega (k \ log (n / k)) $ , combinando com o limite superior para quase todos os valores da matemática $ k $ .

(os algoritmos provavelmente podem ser retirados retirados para dar um limite superior correspondente.)