Fugindo de Nested Loops

Programação
,
#1

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?

#2

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);
}
1 curtida
#3

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.

2 curtidas
#4

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

#5

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!

#6

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

1 curtida
#7

@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.