Um pouco de magia algorítmica antiga ou resolvendo uma sequência intrigante de tarefas do LeetCode

Há algum tempo, me deparei com uma série divertida de tarefas no site leetcode.com. As tarefas em si não são muito difíceis, mas as suas soluções são bastante intrigantes. Além disso, problemas desse tipo aparecem frequentemente em entrevistas em grandes empresas, e compreender os métodos de sua solução pode ser bastante benéfico.

A primeira tarefa é 136. Número único (fácil)

Dada uma matriz não vazia de inteiros onde cada elemento aparece duas vezes, exceto um, você precisa encontrar o elemento sem um par. Resolva o problema em complexidade de tempo O(n) e com memória extra constante.

Exemplo 1:

Entrada: nums = [1, 3, 3, 2, 6, 2, 1]

Saída: 6

Exemplo 2:

Entrada: nums = [12, 1, 1, 7, 1, 12, 1]

Saída: 7

Exemplo 3:

Entrada: números = [6]

Saída: 6

Aproveitaremos a propriedade da função XOR, que produz 1 apenas quando seus operandos são diferentes. Percorrendo todos os elementos do array e executando XOR bit a bit neles, zeraremos todos os valores de bits idênticos. Como resultado, o que resta será o resultado desejado.

Aqui está um pequeno código de solução Python3:

 def single_number(nums: list) -> int: result = 0 for el in nums: result ^= el return result

Usamos apenas a quantidade de memória adicional que um número inteiro ocupa e encontramos a solução em uma única passagem pelo array fornecido, o que nos dá complexidade O(n). Esta é uma solução concisa e elegante.

O segundo problema é 137. Número único II (dificuldade média)

Dado um array não vazio de inteiros onde cada elemento aparece três vezes, exceto um, e apenas um elemento aparece uma vez, precisamos encontrar esse elemento único. Resolva o problema em complexidade de tempo O(n) e com memória extra constante.

Exemplo 1:

Entrada: nums = [3, 1, 3, 3]

Saída: 1

Exemplo 2:

Entrada: nums = [12, 1, 1, 5, 1, 12, 12]

Saída: 5

Exemplo 3:

Entrada: números = [6]

Saída: 6

Infelizmente, não podemos usar o truque anterior neste caso, pois não podemos transformar bits emparelhados na posição necessária em zeros. Seria tentador transformar o array fornecido no formato da tarefa anterior e então resolvê-lo de maneira semelhante.

Raciocinando desta forma, é fácil perceber que se soubéssemos que já havíamos encontrado o número N duas vezes (ou três vezes) ao percorrer o array, poderíamos adicionar um XOR adicional com N à soma que estamos obtendo. Isto tornaria o XOR final com este número par, removendo-o assim da soma final, e o que resta seria a nossa resposta.

 def single_number_ii(nums: list) -> int: mem = {} result = 0 for el in nums: if not mem.get(el, False): mem[el] = 1 else: mem[el] += 1 if mem[el] == 2: result ^= el result ^= el return result

Infelizmente, esta solução exigiria um máximo de (len(nums)-1)/3 em termos de memória, o que não pode ser considerado um consumo constante, por isso teremos que procurar outra solução.

Vamos tentar mudar nossa abordagem.

Anteriormente, usamos XOR (que representa o módulo de adição 2). Se tivéssemos implementado o módulo de adição 3, poderíamos facilmente ter aplicado o truque do exemplo anterior.

Se pudermos colocar um número na resposta na primeira vez que o encontrarmos, colocá-lo no acumulador na segunda vez e zerar a resposta e o acumulador na terceira vez, isso nos ajudaria a resolver o problema de uma só vez. a lista com consumo adicional de memória exatamente igual a dois inteiros, atendendo aos requisitos da tarefa.

Então, vamos aplicar um pouco mais de magia bit a bit:

 def single_number_137_ii(nums: list) -> int: ans, acc = 0, 0 for n in nums: ans = ans ^ n & ~acc acc = acc ^ n & ~ans return ans

Dessa forma, todos os números triplos são zerados e ficamos apenas com o número que ocorre apenas uma vez.

A terceira tarefa é 260. Número Único III (dificuldade média)

Dado um array não vazio de inteiros onde cada elemento aparece duas vezes, exceto dois elementos que aparecem apenas uma vez, precisamos encontrar esses elementos únicos. O objetivo é resolver o problema em complexidade de tempo O(n) e com memória extra constante, e a ordem dos elementos únicos não importa.

Exemplo 1:

Entrada: nums = [1, 2, 1, 3, 2, 5]

Saída: [3, 5]

Exemplo 2:

Entrada: nums = [1, -2]

Saída: [-2, 1]

Obviamente, podemos eliminar facilmente todos os números emparelhados usando a operação XOR, como fizemos na resolução da primeira tarefa. A complexidade da tarefa reside então na identificação de qualquer um dos números únicos, após o qual o segundo pode ser facilmente calculado por meio de XOR com nossa soma XOR.

Para conseguir isso, só precisamos determinar qualquer bit diferente entre esses números únicos. Em seguida, iteramos novamente pelo array, realizando a soma XOR e dividindo os resultados em dois grupos - para números onde este bit está definido e para aqueles onde é 0. Como resultado, obtemos os elementos únicos desejados.

 def single_number_260(nums: list) -> int: res1, res2 = 0, 0 glob_xor = 0 for n in nums: glob_xor ^= n diff_bit = glob_xor & ~(glob_xor - 1) for n in nums: if n & diff_bit: res1 ^= n else: res2 ^= n return [res1, res2]

Apesar de ter que percorrer o array duas vezes, a complexidade permanece O(n) e o consumo de memória é de apenas 2 números inteiros.

NB: Apesar de int em Python não ser exatamente igual a int em outras linguagens, consideraremos seu tamanho como uma constante