[Resolvido]Números duplicados exercício em C

O que está tentando fazer?

Entender o funcionamento da função firsDuplicate, como ela consegue estabelecer o número repetido de menor índice e a utilização desse vetor auxiliar b[100001];

Muito Obrigado peczenyj!!!
Entendi…
incrível… então como é hash a eficiência é O(1).

A função que fiz não passou nos testes de eficiência, quando a entrada ficou enorme(tipo 5000 itens)… kkkkk
-Segue abaixo:

int firstDuplicate(arr_integer a) {
    int valor = -1;
    int indice_anterior = a.size+1;

for(int x = 0; x < a.size; x++){
    for(int y = x + 1; y < a.size; y++){
       if(a.arr[x] == a.arr[y] && y < indice_anterior){             
           valor = a.arr[y]; 
           indice_anterior = y;
       }
    }
}
return valor;
}

Sou novo na área, então não repare nos erros de lógica e otimização que existem no código… se tiver alguma dica de como fazer isto de uma maneira eficiente pf me ajude kkkkkk

vamos la

vc esta fazendo 2 loops. para verificar N items vc vai gastar N ao quadrado.

entretanto vc fez uma mutreta, vc não analisa todo o array no segundo loop, isso garante alguma agilidade.

o problema é: vc deixa seus loops irem ate o fim e ai vai retornar valor, sendo q valor certamente sera do ultimo item duplicado.

se vc encontrou o primeiro duplicado, sai fora logo. da um return la de dentro mesmo. só vai dar ruim se vc tiver algo como 1,2,3,4,… 1000, 1000 ( la no fim )

a unica forma disso ser mais eficiente é se vc pudesse ordenar o vetor de entrada, encontrar valores duplicados é moleza desse jeito. mas ai vc vai ficar limitado a eficiencia do algoritmo de ordenação

Olá, todos!

Uma sinapse com relação ao variável: indice_anterior. Vejo melhor uso na expressão do segundo FOR que na segunda parte da expressão na declaração IF. Porque se não me interessa os índices maiores, apenas os índices menores que o atual são os interessantes, então se jogas com a variável: indice_anterior na expressão do primeiro e último FOR terás melhor aproveitamento dessa lógica.

Pois; todo índice que é maior que o atual deve ser desinteressante. Se eu não estiver errado, acredito que com essa medida, dois - três cálculos computacionais serão economizados.

Att. AnsiC

Legal AnsiC, vou tentar implementar… Mas fiquei empolgado com a ideia do peczenyj, de ordenar o vetor de entrada e depois procurar os números duplicados, parece uma lógica “simples” que resolve o problema de forma eficiente.
Quero usar o QuickSort, vamos ver se a eficiência vai ser alta para uma entrada grande…(ainda não conseguir usar o meu quick está com: “erro de segmentação” kkkkkk)

Ordenar o vetor, não significa perde em sentido a questão?

Vejam bem, se pegarmos este vetor A = [2, 1, 3, 5, 3, 2] e ordenasse ele A´ = [1, 2, 2, 3, 3, 5] não poderíamos dizer que A == A´, em termos de elementos são iguais, mas em termos de arranjos são diferentes porque seus índices são diferentes, dois vetores para um mesmo conjunto.

firstDuplicate (A ) = 3.
firstDuplicate (A´) = 2.

Contudo, se de alguma forma vai preservar; ou faz persistir os índices originais do vetor, mesmo após a organização dele, então é possível não perder em sentido. Pois veja bem que para o exemplo A coube respectivamente duas resposta. Ainda sim por hipótese, não consigo visualizar como alterar os índices e persistir com os valores originais seja viável.

Se estiver errado, por favor me digam onde errei.
Att. AnsiC

verdade…os índices serão modificados…não tinha pensando muito sobre isso…vish