Um elemento que difere em duas matrizes. Como encontrá-lo eficientemente?

Estou me preparando para uma entrevista de codificação e realmente não consigo descobrir a maneira mais eficiente de resolver esse problema.

Digamos que temos duas matrizes que consistem em números que não são classificados. A matriz 2 contém um número que a matriz 1 não. Ambas as matrizes têm números localizados aleatoriamente, não necessariamente na mesma ordem ou nos mesmos índices. Por exemplo:

Matriz 1 [78,11, 143, 84, 77, 1, 26, 35 .... n]

Matriz 2 [11,84, 35, 25, 77, 78, 26, 143 ... 21 ... n + 1]

Qual é o algoritmo mais rápido para encontrar o número que difere? Qual é o seu tempo de execução? Neste exemplo, o número que estaríamos procurando é 21.

Minha ideia era percorrer a Matriz 1 e excluir esse valor da matriz 2. Iterar até terminar. Deve ser em torno de tempo de execução, certo?$O(n \log n)$

Vejo quatro maneiras principais de resolver esse problema, com diferentes tempos de execução:

• Solução O ( n 2 ) : essa seria a solução que você propõe. Observe que, como as matrizes não são classificadas, a exclusão leva tempo linear. Você realiza n exclusões; portanto, esse algoritmo leva tempo quadrático.$O(n^2)$$n$

• solução: classifique as matrizes antecipadamente; em seguida, execute uma pesquisa linear para identificar o elemento distinto. Nesta solução, o tempo de execução é dominado pela operação de classificação, portanto, o O ( $O(n \: log \: n)$ limite superior.$O(n \: log \: n)$

Ao identificar uma solução para um problema, você deve sempre se perguntar: posso fazer melhor? Nesse caso, você pode fazer um uso inteligente das estruturas de dados. Observe que tudo que você precisa fazer é iterar uma matriz e executar pesquisas repetidas na outra matriz. Que estrutura de dados permite que você faça pesquisas em tempo constante (esperado)? Você adivinhou certo: uma tabela de hash .

• solução (esperada): itere a primeira matriz e armazena os elementos em uma tabela de hash; em seguida, execute uma varredura linear na segunda matriz, procurando cada elemento na tabela de hash. Retorne o elemento que não foi encontrado na tabela de hash. Essa solução de tempo linear funciona para qualquer tipo de elemento que você possa passar para uma função hash (por exemplo, funcionaria de maneira semelhante para matrizes de strings).$O(n)$

Se você deseja garantias de limite superior e as matrizes são estritamente compostas por números inteiros, a melhor solução é, provavelmente, a sugerida por Tobi Alafin (embora essa solução não forneça o índice do elemento que difere na segunda matriz) :

• Solução O ( n ) (garantida): some os elementos da primeira matriz. Em seguida, resuma os elementos da segunda matriz. Finalmente, execute a subtração. Observe que esta solução pode realmente ser generalizada para qualquer tipo de dados cujos valores possam ser representados como cadeias de bits de comprimento fixo, graças aooperador XOR bitabit. Isso é completamente explicado naresposta deIlmari Karonen. $O(n)$

Finalmente, outra possibilidade (sob a mesma suposição de matrizes inteiras) seria usar um algoritmo de ordenação em tempo linear, como ordenação por contagem. Isso reduziria o tempo de execução da solução baseada em classificação de a O ( n ) .$O(n \: log \: n)$$O(n)$

O diferença-de-somas solução proposta por Tobi e Mario pode na verdade ser generalizada para qualquer outro tipo de dados para os quais podemos definir um (constante de tempo) operação binária ⊕ que é:$\Theta(n)$$\oplus$

• total , de modo que, para quaisquer valores e b , a ⊕ b seja definido e do mesmo tipo (ou pelo menos de algum supertipo apropriado, para o qual o operador ⊕ ainda esteja definido);$a$$b$$a \oplus b$$\oplus$
• associativo , de modo que ;$a \oplus (b \oplus c) = (a \oplus b) \oplus c$
• comutativo , tal que ; e$a \oplus b = b \oplus a$
• cancelável , de modo que exista um operador inverso que satisfaça ( a ⊕ b ) ⊖ b = a . Tecnicamente, essa operação inversa nem precisa necessariamente ser de tempo constante, desde que "subtraindo" duas somas de n elementos cada uma não demore mais que O ( n ) tempo.$\ominus$$(a \oplus b) \ominus b = a$$n$${\rm O}(n)$

(Se o tipo só pode receber um número finito de valores distintos, essas propriedades são suficientes para transformá-lo em um grupo abeliano ; mesmo se não, será pelo menos um semigrupo comutativo de cancelamento .)

Usando essa operação , podemos definir a "soma" de uma matriz a = ( a 1 , a 2 , … , a n ) como ( $\oplus$$a = (a_1, a_2, \dots, a_n)$ Dada outra matriz b = ( b 1 , b 2 , … , b n , b n + 1 ) contendo todos os elementos de a mais um elemento extra x , temos, portanto, (

Por exemplo, se os valores nas matrizes são números inteiros, em seguida, adição inteiro (ou adição modular para tipos inteiros finito de comprimento) pode ser usado como o operador , com subtracção como a operação inversa ⊖ . Como alternativa, para qualquer tipo de dados cujos valores possam ser representados como cadeias de bits de comprimento fixo, podemos usar o XOR bit a bit como ⊕ e ⊖ .$\oplus$$\ominus$$\oplus$$\ominus$

De maneira mais geral, podemos aplicar o método XOR bit a bit em seqüências de comprimento variável, preenchendo-as com o mesmo comprimento necessário, desde que tenhamos alguma maneira de remover reversivelmente o preenchimento no final.

Em alguns casos, isso é trivial. Por exemplo, cadeias de bytes terminadas nulas no estilo C codificam implicitamente seu próprio comprimento, portanto, aplicar esse método a elas é trivial: ao XORing duas cadeias, preencha a mais curta com bytes nulos para fazer com que seu comprimento corresponda e apare quaisquer nulos à direita extra de o resultado final. Observe que as cadeias intermediárias de soma XOR podem conter bytes nulos; portanto, você precisará armazenar explicitamente seu comprimento (mas precisará apenas de um ou dois deles no máximo).

$1$$0$$0$$1$$2^{32}$bytes, poderíamos codificar o comprimento de cada string como um número inteiro de 32 bits e anexá-lo à string. Ou podemos até codificar comprimentos arbitrários de cadeias usando algum código de prefixo e anexá-los às cadeias. Também existem outras codificações possíveis.

$\Theta(n)$

A única parte potencialmente complicada é que, para que o cancelamento funcione, precisamos escolher uma representação de cadeia de bits canônica exclusiva para cada valor, o que pode ser difícil (de fato, potencialmente até indecidível computacionalmente) se os valores de entrada nas duas matrizes puderem ser dados em diferentes representações equivalentes. Esta não é uma fraqueza específica deste método, no entanto; qualquer outro método para resolver esse problema também poderá falhar se for permitido que a entrada contenha valores cuja equivalência seja indecidível.

Eu postaria isso como um comentário na resposta de Tobi, mas ainda não tenho reputação.

Como alternativa ao cálculo da soma de cada lista (especialmente se forem listas grandes ou contiverem números muito grandes que podem sobrecarregar seu tipo de dados quando somados), você pode usar xor.

Apenas calcule a soma xor (ou seja, x [0] ^ x [1] ^ x [2] ... x [n]) de cada lista e, em seguida, xe esses dois valores. Isso fornecerá o valor do item estranho (mas não o índice).

Ainda é O (n) e evita problemas com o estouro.

Elemento = Soma (matriz2) - Soma (matriz1)

Eu sinceramente duvido que este é o algoritmo mais ideal. Mas é outra maneira de resolver o problema e é a maneira mais simples de resolvê-lo. Espero que ajude.

Se o número de elementos adicionados for mais de um, isso não funcionará.

Minha resposta tem a mesma complexidade de tempo de execução para o melhor, o pior e o médio,

EDIT
Após pensar um pouco, acho que minha resposta é sua solução.

$n$$n-1$$1 = n-1$$2 = n+1 -1=n$

$2n-1$$2 -$$1 = 1$

$2n - 1 + 1 = 2n$

EDIT:
Devido a alguns problemas com os tipos de dados, uma soma XOR conforme sugerida por reffu será mais adequada.

Supondo que a matriz 2 foi criada tomando a matriz 1 e inserindo um elemento em uma posição aleatória, ou a matriz 1 foi criada tomando a matriz 2 e excluindo um elemento aleatório.

Se é garantido que todos os elementos da matriz sejam distintos, o tempo é O (ln n). Você compara os elementos no local n / 2. Se forem iguais, o elemento extra será de n / 2 + 1 até o final da matriz, caso contrário, será de 0 a n / 2. E assim por diante.

Se não for garantido que os elementos da matriz sejam distintos: você pode ter n vezes o número 1 na matriz 1 e o número 2 inserido em qualquer lugar da matriz 2. Nesse caso, você não pode saber onde está o número 2 sem olhar para todos. elementos da matriz. Portanto O (n).

PS. Como os requisitos foram alterados, verifique sua biblioteca para saber o que está disponível. No macOS / iOS, você cria um NSCountedSet, adiciona todos os números da matriz 2, remove todos os números da matriz 1, e o que resta é tudo o que está na matriz 2, mas não na matriz 1, sem confiar na alegação de que há um adicional item.

var mais curto, mais longo;

Converta o mais curto em um mapa para referência rápida e o loop pelo mais longo até que o valor atual não esteja no mapa.

Algo assim em javascript:

if (arr1.length> arr2.length) {menor = arr2; mais longo = arr1; } mais {shortest = arr1; mais longo = arr2; }

var map = shortest.reduce (função (obj, valor) {obj [valor] = verdadeiro; retorna obj;}, {});

var diferença = longest.find (função (valor) {return !!! mapa [valor];});

Solução O (N) em complexidade de tempo O (1) em termos de complexidade de espaço

Declaração do problema: Supondo que a matriz2 contenha todos os elementos da matriz1 mais um outro elemento não presente na matriz1.

A solução é: Usamos xor para encontrar o elemento que não está presente no array1, portanto, as etapas são: 1. Inicie no array1 e execute xor de todos os elementos e os armazene em uma variável. 2. Pegue o array2 e execute o xor de todos os elementos com a variável que armazena o xor do array1. 3. Depois de fazer a operação, nossa variável conterá o elemento que está presente apenas no array2. O algoritmo acima funciona devido às seguintes propriedades de xor "a xor a = 0" "a xor 0 = a" Espero que isso resolva seu problema. Também as soluções sugeridas acima também são boas