java - tamaño - Cómo encontrar el único número en una matriz que no aparece dos veces
numero mayor de una matriz en java (5)
Esta pregunta ya tiene una respuesta aquí:
Lo siguiente está tomado de una entrevista de trabajo:
En una matriz dada, que contiene enteros, cada número se repite una vez, excepto uno, que no se repite. Escribe una función que encuentre el número que no se repite.
Pensé en usar un HashSet, pero podría complicar todo ...
¿Alguna idea de una solución simple?
Aquí hay una forma un poco menos ofuscada de hacerlo:
List list = Arrays.asList(a);
int result;
for(int i:a)
{
if(list.indexOf(i)==list.lastIndexOf(i))
{
result = i;
break;
}
}
result
contendrá el valor no repetido.
He visto esta pregunta antes. Es un truco. Suponiendo que todos los números repetidos aparecen exactamente dos veces, hace esto:
int result = 0;
for (int a : arr)
result ^= a;
La mejor respuesta ya está dada (XOR-ing los elementos), esto es proporcionar una forma alternativa, más general.
Si la matriz de entrada se ordenaría (podemos ordenarla), simplemente podríamos iterar sobre los elementos en pares (paso a paso por 2) y si los elementos del "par" son diferentes, hemos terminado:
public static int findSingle(int[] arr) {
Arrays.sort(arr);
for (int i = 0, max = arr.length - 1; i < max; i += 2)
if (arr[i] != arr[i + 1])
return arr[i];
return arr[arr.length - 1]; // Single element is the last
}
Nota: Esta solución ordena la matriz de entrada; si esto no es deseado o no está permitido, se puede clonar primero:
arr = arr.clone();
Si se ordena la matriz de entrada, la
Arrays.sort(arr)
se puede dejar fuera de curso.
Generalización
La ventaja de esta solución es que se puede aplicar a todos los tipos que son comparables y, por lo tanto, se pueden ordenar (tipos que implementan
Comparable
), por ejemplo,
String
o
Date
.
La solución
XOR
se limita solo a números.
Aquí hay una versión ligeramente modificada que toma una matriz de entrada de cualquier tipo de elemento que sea comparable:
public static <E extends Comparable<E>> E findSingle(E[] arr) {
Arrays.sort(arr);
for (int i = 0, max = arr.length - 1; i < max; i += 2)
if (arr[i].compareTo(arr[i + 1]) != 0)
return arr[i];
return arr[arr.length - 1]; // Single element is the last
}
Nota: En la mayoría de los casos, también puede usar
arr[i].equals(arr[i + 1])
para comparar elementos en lugar de usar
Comparable.compareTo()
.
Para más detalles, lea el enlace javadoc.
Citando la parte relevante:
Se recomienda encarecidamente, pero no es estrictamente necesario que
(x.compareTo(y)==0) == (x.equals(y)). En términos generales, cualquier clase que implemente la interfazComparabley viole esta condición debe indicar claramente este hecho. El lenguaje recomendado es "Nota: esta clase tiene un orden natural que es inconsistente con iguales".
Ahora puede llamar a esto con una
String[]
por ejemplo:
System.out.println(findSingle(new String[] { "1", "2", "3", "1", "3" }));
Salida:
2
Notas finales
A partir de la declaración del problema, no se verifica si hay más de 2 ocurrencias de los elementos, y tampoco si la longitud de la matriz es impar.
Además, el segundo ejemplo no verifica
null
valores
null
, estos se agregarán si es necesario.
Otra solución "ordinaria" (en Java):
public static int findSingle(int[] array) {
Set<Integer> set = new HashSet<Integer>();
for (int item : array) {
if (!set.remove(item)) {
set.add(item);
}
}
assert set.size() == 1;
return set.iterator().next();
}
En mi opinión, la solución con XOR es hermosa.
Este no es tan rápido como XOR, pero el uso de HashSet lo hace cerca de O (n). Y ciertamente es más legible.
Puede definir un "resultado" entero inicializado a 0, y luego realizar algunas operaciones bit a bit aplicando una lógica XOR a todos los elementos de su matriz.
Al final, "resultado" será igual al único elemento que aparece solo una vez.
result = 0
for i in array:
result ^= i
return result
http://en.wikipedia.org/wiki/Bitwise_operation#XOR
Por ejemplo, si su matriz contiene los elementos [3, 4, 5, 3, 4], el algoritmo devolverá
3 ^ 4 ^ 5 ^ 3 ^ 4
Pero el operador XOR ^ es asociativo y conmutativo, por lo que el resultado también será igual a:
(3 ^ 3) ^ (4 ^ 4) ^ 5
Como i ^ i = 0 para cualquier número entero i, e i ^ 0 = i, tiene
(3 ^ 3) ^ (4 ^ 4) ^ 5 = 0 ^ 0 ^ 5 = 5