// typedef struct arr_integer {
// int size;
// int *arr;
// } arr_integer;
//
// arr_integer alloc_arr_integer(int len) {
// arr_integer a = {len, len > 0 ? malloc(sizeof(int) * len) : NULL};
// return a;
// }
Função:
int firstDuplicate(arr_integer a) {
int b[100001] = {0};
int hihi = -1;
for (int i=0; i<a.size; i++) {
if (b[a.arr[i]]) {
hihi = a.arr[i];
break;
}
b[a.arr[i]]++;
}
return hihi;
}
Problema:
Dado um array a que contém apenas números no intervalo de 1 a a.length, encontre o primeiro número duplicado para o qual a segunda ocorrência possui o índice mínimo. Em outras palavras, se houver mais de 1 número duplicado, retorne o número para o qual a segunda ocorrência possui um índice menor do que a segunda ocorrência do outro número. Se não houver tais elementos, retorne -1.
Para a = [2, 1, 3, 5, 3, 2], a saída deve ser firstDuplicate (a) = 3.
Existem 2 duplicatas: números 2 e 3. A segunda ocorrência de 3 tem um índice menor do que a segunda ocorrência de 2, portanto, a resposta é 3.
Para a = [2, 4, 3, 5, 1], a saída deve ser firstDuplicate (a) = -1.
OBS: não fiz essa função, estava tentando resolver umas questões no code fight e alguem resolveu desse modo, mas eu não to conseguindo entender como a função funciona(principalmente o vetor dentro do vetor no if e tals).
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
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
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.
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
