Fugindo de Nested Loops

17 de dezembro de 2018 6 respostas Resolvido

Dahan_Schuster 17 de dezembro de 2018

Boa noite,
estou treinando lógica em um site muito bom chamado Code Signal, onde o usuário é desafiado a resolver problemas de lógica com a maior eficiência possível.

Eu não faço faculdade e não tenho conhecimentos técnicos específicos, então vivo criando soluções não tão eficientes. Mas isso não o problema maior (até porque é por isso mesmo que estou praticando, para melhorar minha eficiência), o problema mesmo é que me vejo impossibilitado de resolver certas questões porque não possuo o conhecimento necessário.

Queria ajuda com nested loops (loops dentro de loops). Este é o segundo código que resolvo e que funciona corretamente, mas a solução não é aceita porque demora muito quando o input é imenso.

Eis o código:

boolean areSimilar(int[] a, int[] b) {
		int[] tempA = Arrays.copyOf(a, a.length);
		for (int k = 0; k < a.length - 1; k++) {
			for (int i = 0; i < tempA.length; i++) {
				tempA = Arrays.copyOf(a, a.length);
				tempA[k] = a[i];
				tempA[i] = a[k];
				if (Arrays.equals(tempA, b))
					return true;
			}
		}
		return false;
	}

A função dele é receber dois vetores de inteiros e dizer se é possível igualar o vetor A ao vetor B apenas trocando de posição dois elementos do vetor A.
Por exemplo, para os vetores A = {1, 2, 3} e B = {2, 1, 3}, pode-se igualá-los apenas trocando de posição os índices 0 e 1 do vetor A.

O código acima faz isso. Rodei os testes do site e todos resultaram o esperado. Porém quando o site testa inputs enormes, com A.length = 100000, por exemplo, o tempo de execução vai às alturas.

Não consigo pensar em alguma forma de otimizar este código, nem achei alguma solução na rede.
Alguém pode me ajudar?

6 Respostas

rodevops 17 de dez. de 2018 1 like

Fugirá um pouco da regra, mas não seria mais facil ordenar os dois vetores e compara-los no final?

boolean areSimilar(int[] a, int[] b) {
    int[] tempA = Arrays.copyOf(a, a.length);
    int[] tempB = Arrays.copyOf(b, b.length);
    Arrays.sort(tempA);
    Arrays.sort(tempB);
    return Arrays.equals(tempA, tempB);
}

Agora se quiser aumentar a performance e não ter problemas em ordenar os arrays “originais” basta:

boolean areSimilar(int[] a, int[] b) {
    Arrays.sort(a);
    Arrays.sort(b);
    return Arrays.equals(a, b);
}

Solucao aceita

AbelBueno 17 de dez. de 2018 2 likes

Você pode estudar sobre complexidade de algoritmos (procure sobre notaçao Big O) para ter uma idéia de como o algoritmo escala.

Para ter uma idéia, no seu código, digamos que o tamanho do array a ou b é N, para cada elemento de a, você executará N açoes pelo menos (por causa do nested loop), ou seja o número de açoes que seu código executa é no mínimo N * N. Por isso a complexidade do seu algoritmo é basicamente quadrática (N ao quadrado) o que nao é nada eficiente.

Uma maneira de aumentar a eficiência do algoritmo é reduzir o número de operaçoes que ele faz e eliminar nested loops é uma boa maneira de fazer isso.

Seu código hoje, para cada elemento do array gera uma nova versao dele, trocando duas posiçoes e comparando com B. Você precisa realmente fazer tudo isso?

Você já sabe que os arrays terao apenas dois elementos diferentes um do outro. Com um loop simples você pode

percorrer ambos arrays ao mesmo tempo e verificar que a maioria dos seus elementos sao iguais, guardando o indíce da primeira e segunda diferença
se nao houver diferença, imagino que os arrays sao similares
se tiver duas diferenças, o valor da primeira diferença em a tem de ser o valor da segunda diferença em b (e vice versa)
qualquer outro cenário, os arrays nao sao similares.

Com essa lógica, a complexidade do algoritmo vira linear, pois o número de açoes é basicamente o tamanho do array.

Dahan_Schuster 17 de dez. de 2018

Na verdade, eu não sei se os vetores terão apenas dois elementos diferentes. Esse é o dever do método: descobrir se é possível igualar os dois vetores trocando de posição apenas dois elementos de um deles.
Os inputs podem ser a = {1, 2, 3} e b = {1, 1, 3}, por exemplo. Nesse caso, é impossível igualá-los.

O conceito de O(1), O(n) e O(n*n) eu “conheço” (sei do que se trata, mas não à fundo). O problema é saber como evitar kkkkk

Gostei dessa ideia de percorrer ambos os vetores ao mesmo tempo e verificar as diferenças, vou apostar nela e digo o resultado. Muito obrigado!

A propósito, o link para a questão é esse (esqueci de incluir na pergunta, perdão): CodeSignal - Arcade level 16

Dahan_Schuster 17 de dez. de 2018

Usando o método sort eu estaria trocando de lugar mais de dois índices, o que eu não posso fazer. O dever é descobrir se dá pra igualar os vetores trocando apenas dois índices.

Por exemplo: para a = {7, 8, 9, 10} e b = {10, 9, 7, 8}, o retorno deve ser false, já que para igualar os vetores eu teria que reorganizar todos os índices. Se eu usar o sort(), o retorno seria true.

Agora, para a = {7, 10, 9, 8} e b = {7, 8, 9, 10}, o retorno deve ser true, já que basta trocar os índices 1 e 3 de posição.

Mas obrigado pela disposição em ajudar e pela explicação detalhada! Aprecio muito esse espírito empático nas pessoas!

rodevops 17 de dez. de 2018 1 like

Eu entendi o problema por isso te falei que fugiria da regra, mas enfim, vale para conhecer outras formas de fazer, sucesso!

Dahan_Schuster 18 de dez. de 2018

@AbelBueno consegui! Segui sua dica e fiz esse código:

boolean areSimilar(int[] a, int[] b) {
	int aDifferent = -1; // 1 <= a[n] <= 1000 
	int bDifferent = -1; // 1 <= b[n] <= 1000
	int differenceFoundCount = 0;

	boolean output = true;

	for (int k = 0; k < a.length; k++) {
		if (a[k] != b[k]) {
                differenceFoundCount++;
                if (a[k] == bDifferent && b[k] == aDifferent) {
				output = true;
		} else if (differenceFoundCount > 1) return false;
				
		aDifferent = a[k];
		bDifferent = b[k];
		}
	}
	return output;
}

Devem haver formas mais eficientes de se fazer, mas ao menos consegui consegui enviar a resposta.
Muito obrigado pela dica, aprendi muito resolvendo essa questão.

Criado 17 de dezembro de 2018

Ultima resposta 18 de dez. de 2018

Respostas 6

Participantes 3

6 Respostas

Topicos relacionados