encuentra el único elemento no emparejado en la matriz

Pregunta de la entrevista de Accenture:

Se te ha dado una matriz de tamaño 2n+1 que tiene n par de enteros (puede ser +ve , -ve o 0 ) y un elemento no apareado.

¿Cómo encontrarías el elemento desapareado?

Par significa duplicar . Entonces (3,3) es un par y (3,-3) no es un par.

Toma XOR de todos los elementos.

Los pares se cancelarán como

 a XOR a = 0 

y el resultado será el único elemento no apareado como

 0 XOR a = a 

Si está bien destruir la matriz, puedes XOR elementos adyacentes. Una vez hecho, el último elemento de la matriz tiene el elemento no apareado:

 N = Num of elements in array. for( i=1 to N ) arr[i] ^= arr[i-1]; print arr[N-1] 

Si no está bien destruir la matriz, puede usar una variable para contener el resultado:

 N = Num of elements in array. Unpaird = arr[0]; for( i=1 to N ) Unpaird = Unpaird ^ arr[i]; print Unpaird 

Función C para hacer lo mismo:

 int findUnpaird(int *arr,int len) { int i; // loop counter. int unpaird; // to hold the unpaird element. unpaird = arr[0]; // initialize it with the 1st array ele. for(i=1;i 

Solución alternativa, para encontrar todos los valores únicos en el espacio O (n) y O (n):

Inicializa una tabla Hash.
Para cada valor en la matriz, verifique si el valor existe en la tabla hash, si lo hace, elimínelo, si no lo hace, agréguelo.
El valor de retorno es todos los elementos dentro de la tabla Hash.

Se puede modificar fácilmente para usar un diccionario si los valores recurrentes pueden repetirse más de una vez.

Ejemplo de línea única Linq con una solución XOR:

Demostración en DotNetFiddle

 public static void Main() { int[] tab = { 1, 2, 3, 2, 1 }; Console.WriteLine(GetSingle(tab)); } private static int GetSingle(IEnumerable tab) { return tab.Aggregate(0, (current, i) => current ^ i); } 

Para divertirse y obtener ganancias

Editar:

Explicación para este fragmento.

 var a = 2; var b = 2; Console.WriteLine(a ^ b); // will print 0 // because x ^ x == 0 var c = 3; Console.WriteLine(a ^ b ^ c); // will print 3 // because 0 ^ x == x Console.WriteLine(0 ^ a); // guess the output // get it? :) // Now, lets aggregate this enumerable ;) 

La mejor respuesta es el operador XOR. Solo por diversión, otra forma es, si tiene permitido ordenar la matriz, ordenarla y comparar números enteros adyacentes. Esto supone que todos los enteros aparecen exactamente dos veces con un entero que aparece una vez.

 // Random array of integers int[] arr = {1, 2, 3, 4, 5, 6, 7, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // Sort the array. Arrays.sort(arr); // Array now looks like: 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 9 9 // Cycle through array comparing adjacent values. for(int i = 0; i < arr.length; i++){ // This would mean the single number was the last element in the array. if(i == arr.length-1) singleNum = arr[i]; // If the adjacent elements are the same, skip foward. if(i < arr.length-1 && arr[i] == arr[i+1]) i ++; else // Otherwise, you found the single number. singleNum = arr[i]; } 

Aquí hay una solución LINQ simple que puede ampliarse fácilmente para proporcionar la cantidad de ocurrencias de cada elemento único:

  int[] numbers = { -1, 0, 1, 2, 3, 4, 5, 4, 3, 2, 1 }; var numberGroups = from n in numbers group n by n into g select new { Number = g.Key, IsPaird = g.Count() == 2 }; Console.WriteLine("Unpaird elements:"); foreach (var group in numberGroups) { if (!group.IsPaird) Console.WriteLine(group.Number); } 

Salida:

 Unpaird elements: -1 0 5 

Realice XOR entre todos los elementos de la matriz dada

 def unpaird(arr): result = 0 for i in arr: result = result^i return result 

También es una buena solución. En este ejemplo, tenemos un pasaje de ciclo.

 function getUpaird(arr) { var obj = {}; for (var i = 0; i < arr.length; i++) { if (typeof obj[arr[i]] !== 'undefined') { delete obj[arr[i]]; continue; } obj[arr[i]] = i; } return Number(Object.keys(obj)[0]); } getUpaired([0,0,2,1,3,2,1]);