Determinando o número específico em

$\newcommand\ldotd{\mathinner{..}}$ Dado que $A[1\ldotd n]$ são números inteiros tais que $0\le A[k]\le m$ para todos os $1\le k\le n$ , e a ocorrência de cada número, exceto um número específico em $A[1\ldotd n]$ é um número ímpar. Tente encontrar o número cuja ocorrência é um número par.

Existe um algoritmo $\Theta(n\log n)$ : classificamos $A[1\ldotd n]$ em $B[1\ldotd n]$ e quebre $B[1\ldotd n]$ em várias partes, cujo valor dos elementos é o mesmo, portanto, podemos contar a ocorrência de cada elemento.

Eu quero encontrar um algoritmo de pior caso $O(n)$ -time-and- $O(n)$ -espaço.

Supondo que $m=\Omega(n^{1+\epsilon})$ e $\epsilon>0$ , portanto, a classificação do radical não é aceitável. $\DeclareMathOperator{\xor}{xor}$ Operações binárias bit a bit são aceitáveis, por exemplo, $A[1]\xor A[2]$ .

algorithms search-algorithms Yai0Phah
fonte

A resposta de Aryabhata abaixo mostra que o caso geral não é bom, mas talvez você tenha outras restrições disponíveis? Uma restrição simples (mas grande) seria impor que todas as entradas na matriz tenham tamanho

O (n)

$O(n)$ . Isso daria um algoritmo linear bastante trivial.

Luke Mathieson

@LukeMathieson: apaguei essa resposta, pois ainda não estou convencido de que o trabalho que citei funcionará sem nenhuma modificação e, além disso, o OP parece estar interessado apenas no modelo de custo uniforme da RAM.

Aryabhata

@Aryabhata: hehe, bem, a resposta que não está lá então! Fora de interessante, e talvez útil para Frank, qual você achou que foi o problema de adaptar o resultado no artigo? Uma rápida olhada sugeriu que se aplicava, mas eu obviamente não entendi.

Luke Mathieson

@LukeMathieson: O fato de os outros elementos precisarem aparecer um número ímpar de vezes no problema atual. Uma vez que, eu desnatado sobre a prova também ...

Aryabhata

Seria interessante se você estiver interessado em resultados teóricos ou em soluções práticas. Do ponto de vista da teoria, minha primeira resposta rápida é que você pode classificar uma lista de números inteiros mais rapidamente que

. Há um algoritmo determinístico de Han que é executado no tempo

. Para algoritmos aleatórios, resultados ainda melhores são conhecidos, por exemplo, Han e Thorup encontraram um

O (n \log n)

$O(n\log n)$

O (\log \log n)

$O(\log\log n)$

algoritmo de tempo esperado. No entanto, acho que seu problema não deve exigir classificação.

O (n \sqrt{\log \log n})

$O(n \sqrt{\log\log n})$

A.Schulz

Respostas:

Aqui está uma idéia para um algoritmo simples; apenas conte todas as ocorrências!

$m = \max A$ $\Theta(n)$
"Alocar" matriz . - hora ¹ $C[0..m]$ $O(1)$
Itere sobre e aumente em um sempre que encontrar . Se foi , adicione para uma lista linear . - tempo $A$ $C[x]$ $A[\_]=x$ $C[x]$ $0$ $x$ $L$ $\Theta(n)$
Itere sobre e encontre o elemento com par. - hora . $L$ $x_e$ $C[x_e]$ $O(n)$
Retornar . $x_e$

Em suma, isso fornece um algoritmo de tempo linear que pode usar (no sentido de alocar) muita memória. Observe que ser capaz de acessar aleatoriamente em tempo constante, independentemente de é crucial aqui. $C$ $m$

Um ligado ao espaço é mais difícil com essa abordagem; Não conheço nenhuma estrutura de dados do dicionário que ofereça pesquisa de tempo . Você pode usar tabelas de hash para a qual aqui são implementações com esperado lookup tempo ( tamanho da tabela, o número de elementos armazenados) para que possa obter arbitrariamente bom com espaço linear - na expectativa. Se todos os valores em mapearem o mesmo valor de hash, você estará ferrado. $O(n)$ $O(1)$ $O(1 + k/n)$ $n$ $k$ $A$

Em uma RAM, isso é feito implicitamente; tudo o que precisamos é a posição inicial e talvez a posição final.

Rafael
fonte

Uma solução quase trivial - que usa o espaço - é usar um mapa de hash. Lembre-se de que um mapa de hash amortizou o tempo de execução para adicionar e procurar elementos. $\Theta(n)$ $\mathcal{O}(1)$

Portanto, podemos usar o seguinte algoritmo:

Alocar um mapa de hash . Iterar . Para cada elemento , aumente o número de ocorrências vistas, ou seja, . $H$ $A$ $i \in A$ $H(i)++$
Itere o conjunto de chaves do mapa de hash e verifique qual das chaves possui uma contagem uniforme de ocorrências.

Agora, esse é um algoritmo simples, que não usa truques grandes, mas às vezes é o suficiente. Caso contrário, você pode especificar quais restrições de espaço impõe.

HdM
fonte

Eu ainda gostaria de saber se existe um algoritmo de tempo não randomizado usando espaço polinomial. Em particular, existe alguma evidência teórica de que encontrar o único item de ocorrência par seja mais difícil do que encontrar o único item de ocorrência ímpar?

O (n)

$O(n)$

A.Schulz

@ A.Schulz Eu acho que é o algoritmo de tempo esperado usando tabela de hash. Lembro que alguém me disse um algoritmo (ou, em algum caso especial, digamos, ímpar = 1 e par = 2) talvez com pilha, mas não consigo me lembrar.

O (n)

$O(n)$

O (n)

$O(n)$

Yai0Phah

Nem toda implementação de hashtable possui essa propriedade; geralmente, a pesquisa não é , nem é amortizada (afaik). De fato, uma discussão anterior não resultou em nenhuma implementação com pesquisa de tempo constante. Você pode ser mais específico?

O (1)

$O(1)$

Raphael