BastterCode semana 12 - 645. Set Mismatch
comentada em 02/05/2023 16:56

public class Solution {
    public int[] FindErrorNums(int[] nums) {
        var p = new HashSet<int>();

        int repeated = 0;

        for (int i = 0; i < nums.Length; i++) {
            if (p.Contains(nums[i]))
                repeated = nums[i];
            p.Add(nums[i]);
        }

        for (int i = 1; i <= nums.Length; i++) {
            if (!p.Contains(i))
                return new int[] { repeated, i };
        }

        return null;
    }
}

C# feijão com arroz mesmo.

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        expected = [0] * len(nums)
        for i in nums:
            if expected[i-1] == 0:
                expected[i-1] = i
            elif expected[i-1] == i:
                duplicated = i
        missing = expected.index(0) + 1    

        return [duplicated, missing]

Ver mais

postado por @PMHM em 14/04/2023 20:59

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        expected = [0] * len(nums)
        for i in nums:
            if expected[i-1] == 0:
                expected[i-1] = i
            elif expected[i-1] == i:
                duplicated = i
        missing = expected.index(0) + 1    

        return [duplicated, missing]

Ver mais

Não entendi:

missing = expected.index(0) + 1 ?

pq isso é o missing?

- A gente cria uma lista de 0s com o tamanho n.
- Para cada elemento encontrado em `nums` a gente coloca ele na posição esperada, exceto dois casos:
   1- Se a gente tenta colocar o i e ele já está lá, então é o duplicado
   2- O número que não está em nums nunca é inserido em expected, então permanece como 0

Ao final do loop, a posição da lista de 0s que continuou 0 é o número que faltou... (o index(0) retorna a posição da lista cujo valor é 0). Versão modificada, com output da lista expected

def findErrorNums(nums):
    expected = [0] * len(nums)
    for i in nums:
        if expected[i-1] == 0:
            expected[i-1] = i
        elif expected[i-1] == i:
            duplicated = i
    missing = expected.index(0) + 1    

    print(expected)

tests = [
    [1,2,2,4],
    [1,3,3,4],
    [3,1,1],
    [1,1],
]

for test in tests:
    findErrorNums(test)

Output:

[1, 2, 0, 4]
[1, 0, 3, 4]
[1, 0, 3]
[1, 0]

boa sacada! não tinha pensado nisso.

 

Fiz assim:

Criei um vetor de booleans em que cada índice corresponde a um número no intervalo dado pelo problema.

Percorro os números do vetor informado e vou ligando o índice correspondente do vetor de booleans. Quando encontro um índice duplicado, empurro o número correspondente no vetor solução.

Além disso, vou somando os valores dos números do vetor informado e ao final comparo com a soma esperada para os n primeiros números naturais.

Se os n primeiros números naturais forem imaginados como uma sequência finita A e o vetor informado for outra sequência finita B, todos os números serão iguais entre A e B, à exceção do número repetido (que aparece duas vezes em B e só uma em A) e do número faltante (que aparece uma vez em A e nenhuma em B).

Logo, a diferença entre a soma esperada e a soma encontrada elimina todos os números que são iguais entre ambas as listas e resulta em af - ar, em que af é o número faltante e ar é o número repetido. Como já encontramos o número repetido e empurramos no vetor solução, basta somar o primeiro elemento do vetor solução para termos af - ar + ar = af, que é o número faltante.

Aí empurramos esse número faltante no vetor solução e temos a resposta.

Fiz um for com dois iteradores, para poder percorrer o vetor de números com complexidade logarítmica.

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        vector<bool> elements(nums.size(), false);
        vector<int> sol{};
        int sum_tot = (nums.size()*(nums.size()+1))/2;
        int sum_nums = 0;
                
        ::vector<int>::iterator finish = nums.end();
        for (::vector<int>::iterator start = nums.begin(); start != finish; ++start) {
            if (elements[*start]) sol.push_back(*start);
            else elements[*start] = true;
            sum_nums += *start;
            
            if (finish >= start + 2) {
                --finish;
                if (elements[*finish]) sol.push_back(*finish);
                else elements[*finish] = true;
                sum_nums += *finish;
            }
        }
        
        sol.push_back(sum_tot - sum_nums + sol[0]);
        return sol;
    }
};?

class Solution:
    def findErrorNums(self, nums: list[int]) -> list[int]:
        n, i = sorted(nums), 0
        while n[i] != n[i + 1]: i += 1
        return [n[i]] + list(set(range(1, len(n) + 1)).difference(n))

A minha solução ficou parecida com a do @FlyCavok, mas super interessante ver outras abordagens, me faz pensar fora da caixinha :)

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        vector<bool> set(nums.size()+1, false);

        int i, dup = 0;
        for (i = 0; i < nums.size(); i++) {
            if (set[nums[i]]) {
                dup = nums[i];
            }
            set[nums[i]] = true;
        }

        for (i = 1; i <= nums.size(); i++) {
            if (!set[i]) {
                break;
            }
        }

        return {dup, i};
    }
};

@Blinx

Tem um pequeno erro no meu código. Eu construí o vetor de booleanos com o tamanho do vetor input (digamos, n). Mas os índices são os valores do vetor input, que vão de 1 até o tamanho n desse vetor input.

Como os vetores em C++ são 0-indexados, então fica faltando "espaço" para o elemento de valor n. O correto teria sido construir o vetor de booleanos com tamanho n+1 ou assONciar os números do vetor input com o índice do vetor de booleanos igual ao valor desses números -1.

Só vi esse erro depois. E ele não pegou quando rodei o programa no leetcode, ou seja, falha dos test cases deles lá.

@Giovanni

Sugerindo 3 Easy:

Reverse Linked List - LeetCode

Move Zeroes - LeetCode

Number of Good Pairs - LeetCode
Para o desafio mensal (Medium):

Combination Sum - LeetCode

Quando fui fazer a questão pela primeira vez, percebi o seguinte.

O input da questão é um vetor de n elementos e cada um desses elementos é um inteiro entre 1 e n, com uma única repetição e um único elemento faltante. Isso significa que existe quase uma bijeção entre os índices do vetor e os valores do vetor.

Na época eu pensei que poderia explorar isso para mapear os elementos faltante e repetido, sem precisar do apoio de outra estrutura de dados, ou seja, sem um outro vetor, mapa ou o que for. Mas eu não consegui pensar em uma forma de fazer isso na hora e não tive tempo desde então pra mexer no problema de novo.

Agora de tarde, aproveitei uma folga na minha agenda corrida de pai de dupla jornada e tirei um tempo pra pensar no assunto. Apareceu uma ideia: eu poderia usar o sinal dos valores como uma informação adicional.

A ideia é a seguinte, eu percorro o vetor pela frente e por trás ao mesmo tempo. A cada iteração, eu pego o valor do vetor naquele índice. Depois vou para o índice correspondente a esse valor e mudo o sinal lá para negativo.

Dessa forma, uma vez que eu tiver passado uma vez por todos os índices do vetor,  a partir daí todos os valores dele correspondentes a números de 1 a n contidos no vetor serão negativos. O único valor positivo do vetor corresponderá a um índice que não é valor do vetor, ou seja, será o número faltante.

Além disso, enquanto eu tiver passando pela primeira vez os índices do vetor, se eu for mudar o sinal de um valor e esse sinal já for negativo, significa que o número correspondente a esse índice já apareceu anteriormente. Ou seja, o índice desse valor é o número repetido.

O código é o seguinte:

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        vector<int> sol{};
        
        int end = nums.size();        
        for (int start = 0; start < nums.size(); ++start) {
            int index;
           
            if (start < end) {
                if (nums[start] > 0) index = nums[start] - 1;
                else index = -nums[start] - 1;
                
                if (nums[index] > 0) nums[index] = -nums[index];
                else sol.push_back(index + 1);
            }
            else {
                if (nums[start] > 0) sol.push_back(start + 1);
            }
            
            --end;
            
            if (end > start) {
                if (nums[end] > 0) index = nums[end] - 1;
                else index = -nums[end] - 1;
                
                if (nums[index] > 0) nums[index] = -nums[index];
                else sol.push_back(index + 1);
            }
            else {
                if (nums[end] > 0) sol.push_back(end + 1);
            }
           
        }
        return sol;
    }
};?

Exemplo:

O vetor é o seguinte:

ÍNDICE 0 1 2 3 4
VALOR 1 2 3 5 2

Nesse exemplo, o número repetido é 2 e o número faltante é 4.

Eu começo percorrendo pela frente e por trás:

nums[0] = 1 e nums[4] = 2.

Como os vetores são 0-indexados, então o primeiro elemento é o de índice 0, assim como o n-ésimo elemento é o de índice n - 1. Ou seja, eu subtraio 1 do valor para encontrar o índice.

Logo, eu vou em nums[0], que é o índice correspondente a 1 - 1, e em nums[1], que é o índice correspondente a 2 - 1, e troco o sinal. O vetor passa a ser:

ÍNDICE  0  1  2 3 4
VALOR -1 -2 3 5 2

Continuo percorrendo, agora olho nums[1] pela frente e nums[3] por trás.

nums[1] = -2 e nums[3] = 5.

Como nums[1] é negativo, eu troco o sinal de novo antes de subtrair 1 para achar o índice. Logo, os índices ficam:

-(-2) - 1 = 1 e 5 - 1 = 4

Vou em nums[1] e percebo que o sinal do valor lá já é negativo, é -2. Logo, significa que o número correspondente ao índice 1, ou seja, 2, é repetido. Então já empurro esse valor no vetor solução.

Vou em nums[4] e troco o sinal lá. O vetor passa a ser:

ÍNDICE  0  1  2 3  4
VALOR -1 -2 3 5 -2

Então eu continuo percorrendo, falta apenas nums[2], que é 3. Troco o sinal correspondente ao índice 3 - 1 = 2. O vetor fica:

ÍNDICE  0  1   2 3  4
VALOR -1 -2 -3 5 -2

A partir daí, todos os números do vetor já foram percorridos uma vez. Mas eu continuo percorrendo para encontrar o valor positivo. O índice correspondente a esse valor positivo é de um número que não aparece no vetor, ou seja, o elemento faltante.

Na próxima iteração, chego em nums[3], que é positivo. Logo, o número faltante é o correspondente ao índice 3. Da mesma forma que para chegar no índice eu reduzo em um o número, para chegar ao número eu somo um ao índice. Então o número faltante é 3 + 1 = 4.

Empurro esse número no vetor solução e tenho a resposta: {2,4}.

Essa solução é mais eficiente? Acho que não. Na vida real vale a pena o trabalho? Acho que não.

Mas foi divertido pra caramba resolver essa puzzle kkkk