algorithm - sobre - encuentra el único elemento no emparejado en la matriz

test de futbol 2017

Question

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.

Answer 1

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, IsPaired = g.Count() == 2 };

     Console.WriteLine("Unpaired elements:");
     foreach (var group in numberGroups)
     {
        if (!group.IsPaired)
           Console.WriteLine(group.Number);
     }

Salida:

Unpaired elements:
-1
0
5

Answer 2

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<int> 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 ;)

Answer 3

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];
}

Answer 4

Realice XOR entre todos los elementos de la matriz dada

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

Answer 5

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.

Answer 6

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

function getUpaired(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]);

Answer 7

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.
Unpaired = arr[0];
for( i=1 to N )
   Unpaired = Unpaired ^ arr[i];    
print Unpaired

Función C para hacer lo mismo:

int findUnpaired(int *arr,int len) {
 int i;                  // loop counter.
 int unpaired;           // to hold the unpaired element.

 unpaired = arr[0];      // initialize it with the 1st array ele.

 for(i=1;i<len;i++) {    // loop for all remaining elements.
    unpaired ^= arr[i];  // XOR each element with the running XOR.
 }
 return unpaired;        // return result.
}