Encontrar um único número em uma lista [duplicado]

Question

Essa pergunta já tem resposta aqui:

• Como encontrar o único número em uma matriz que não ocorre duas vezes [duplicado] 5 respostas

Qual seria o melhor algoritmo para encontrar um número que ocorre apenas uma vez em uma lista onde todos os outros números ocorrem exatamente duas vezes.

Portanto, na lista de inteiros (vamos considerar um array) cada inteiro se repete exatamente duas vezes, exceto um.Para descobrir qual é o melhor algoritmo.

Answer 1

A maneira mais rápida (O(n)) e com maior eficiência de memória (O(1)) é com a operação XOR.

Em C:

int arr[] = {3, 2, 5, 2, 1, 5, 3};

int num = 0, i;

for (i=0; i < 7; i++)
    num ^= arr[i];

printf("%i\n", num);

Isso imprime "1", que é o único que ocorre uma vez.

Isso funciona porque na primeira vez que você acerta um número, ele marca a variável num consigo mesmo e na segunda vez ele desmarca num consigo mesmo (mais ou menos).O único que permanece desmarcado é o seu não duplicado.

Answer 2

A propósito, você pode expandir essa ideia para encontrar rapidamente dois números exclusivos entre uma lista de duplicatas.

Vamos chamar os números únicos de a e b.Primeiro pegue o XOR de tudo, como sugeriu Kyle.O que obtemos é a^b.Sabemos que a^b!= 0, já que a!= b.Escolha qualquer bit de a^b e use-o como máscara - com mais detalhes:escolha x como uma potência de 2 para que x & (a^b) seja diferente de zero.

Agora divida a lista em duas sublistas - uma sublista contém todos os números y com y&x == 0, e o restante vai para a outra sublista.A propósito, escolhemos x, sabemos que a e b estão em grupos diferentes.Também sabemos que cada par de duplicatas ainda está no mesmo intervalo.Portanto, agora podemos aplicar o velho truque "XOR-em-all" a cada balde de forma independente e descobrir o que são a e b completamente.

Bam.

Answer 3

O(N) tempo, O(N) memória

HT = tabela hash

Ht.clear () revise a lista para cada item que você vê

if(HT.Contains(item)) -> HT.Remove(item)
else
ht.add(item)

no final, o item do HT é o item que você procura.

Nota (crédito @Jared Updike):Este sistema encontrará todas as instâncias ímpares de itens.

---

Comente:Não vejo como as pessoas podem votar em soluções que proporcionem desempenho NLogN.em qual universo isso é "melhor"?Estou ainda mais chocado por você ter marcado a solução NLogN da resposta aceita ...

Concordo, no entanto, que se a memória for constante, então NLogN seria (até agora) a melhor solução.

Answer 4

A solução de Kyle obviamente não detectaria situações em que o conjunto de dados não seguisse as regras.Se todos os números estivessem em pares, o algoritmo daria um resultado zero, exatamente o mesmo valor como se zero fosse o único valor com ocorrência única.

Se houvesse vários valores de ocorrência única ou triplos, o resultado também seria errôneo.

Testar o conjunto de dados pode resultar em um algoritmo mais caro, seja em memória ou em tempo.

A solução do Csmba mostra alguns dados de erro (nenhum ou mais de um único valor de ocorrência), mas não outros (quádruplos).Quanto à sua solução, dependendo da implementação do HT, ou a memória e/ou o tempo é maior que O(n).

Se não pudermos ter certeza sobre a exatidão do conjunto de entrada, classificar e contar ou usar uma tabela hash de ocorrências de contagem com o próprio número inteiro sendo a chave hash seria viável.

Answer 5

Eu diria que usar um algoritmo de classificação e depois percorrer a lista classificada para encontrar o número é uma boa maneira de fazer isso.

E agora o problema é encontrar o “melhor” algoritmo de classificação.Existem muitos algoritmos de classificação, cada um deles com seus pontos fortes e fracos, então esta é uma questão bastante complicada.O Entrada da Wikipédia parece uma boa fonte de informações sobre isso.

Answer 6

Implementação em Ruby:

a = [1,2,3,4,123,1,2,.........]
t = a.length-1
for i in 0..t
   s = a.index(a[i])+1
   b = a[s..t]
   w = b.include?a[i]
   if w == false
       puts a[i]
   end
end

Answer 7

Você precisa especificar o que entende por "melhor" - para alguns, a velocidade é tudo o que importa e qualificaria uma resposta como "melhor" - para outros, eles poderiam perdoar algumas centenas de milissegundos se a solução fosse mais legível.

"Melhor" é subjetivo, a menos que você seja mais específico.

---

Dito isto:

Itere pelos números, para cada número pesquise esse número na lista e quando você atingir o número que retorna apenas 1 para o número de resultados da pesquisa, estará pronto.

Answer 8

Parece que o melhor que você pode fazer é percorrer a lista, para cada item adicioná-lo a uma lista de itens "vistos" ou então removê-lo do "visto" se já estiver lá, e no final sua lista de "visto "os itens incluirão o elemento singular.Isto é O(n) em relação ao tempo en em relação ao espaço (na pior das hipóteses, será muito melhor se a lista estiver ordenada).

O fato de serem números inteiros não é levado em consideração, já que não há nada de especial que você possa fazer ao somá-los...existe?

Pergunta

Não entendo por que a resposta selecionada é "melhor" em qualquer padrão.O(N*lgN) > O(N), e altera a lista (ou então cria uma cópia dela, que é ainda mais cara em espaço e tempo).Estou esquecendo de algo?

Answer 9

Depende de quão grandes/pequenos/diversos são os números.Uma classificação radix pode ser aplicável, o que reduziria em grande parte o tempo de classificação da solução O (N log N).

Answer 10

O método de classificação e o método XOR têm a mesma complexidade de tempo.O método XOR é apenas O(n) se você assumir que o XOR bit a bit de duas strings é uma operação de tempo constante.Isso equivale a dizer que o tamanho dos inteiros na matriz é limitado por uma constante.Nesse caso, você pode usar a classificação Radix para classificar o array em O(n).

Se os números não forem limitados, então o XOR bit a bit leva o tempo O(k), onde k é o comprimento da string de bits, e o método XOR leva O(nk).Agora, novamente, a classificação Radix classificará o array no tempo O (nk).

Answer 11

Você poderia simplesmente colocar os elementos do conjunto em um hash até encontrar uma colisão.Em Ruby, esta é uma linha única.

def find_dupe(array)
  h={}
  array.detect { |e| h[e]||(h[e]=true; false) }
end

Então, find_dupe([1,2,3,4,5,1]) retornaria 1.

Na verdade, esta é uma pergunta "capital" comum em entrevistas.Normalmente trata-se de uma lista de números inteiros consecutivos com uma duplicata.Neste caso, o entrevistador muitas vezes procura que você use a soma gaussiana de ntruque de números inteiros, por ex. n*(n+1)/2 subtraído da soma real.A resposta do livro é algo assim.

def find_dupe_for_consecutive_integers(array)
  n=array.size-1   # subtract one from array.size because of the dupe
  array.sum - n*(n+1)/2
end