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

Question

Esta pregunta ya tiene una respuesta aquí:

• encuentra el único elemento no emparejado en la matriz 8 respuestas

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?

Answer 1

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.

Answer 2

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;

Answer 3

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 interfaz Comparable y 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.

Answer 4

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.

Answer 5

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