Para una versión más general de este problema (sin esos límites tontas):
Usted puede hacer esto en el tiempo O (n) y O (1) espacio sin asumir ninguna límites, o iterando sobre todos los bits, y usando solo O (1) trucos de manipulación de bit de tiempo como el truco de XOR que funcionó para 2 números faltantes.
Aquí es código (pseudo) para encontrar sólo uno de los números:
// Given an array arr with 2k+3 numbers, k of which are repeated twice
// and the remaining three are distinct: a,b,c.
// returns one of a,b,c.
int FindUnique(int []arr) {
int s = 0; // This will ultimately hold a^b^c (bitwise XOR)
for (int i = 0; i < arr.Length; i++) {
s ^= arr[i];
}
int d = 0; // this holds diff(a,s)^diff(b,s)^diff(c,s)
for (int i = 0; i < arr.Length; i++) {
d ^= diff(arr[i],s);
}
int e = lowestBit(d); // This gives the position where one of a,b,c differs
// from the others.
int bucket1 = 0;
int bucket2 = 0;
for (int i = 0; i < arr.Length; i++) {
if (arr[i] & e) {
bucket1 ^= arr[i];
} else {
bucket2 ^= arr[i];
}
}
int count1 = 0;
int count2 = 0;
for (int i = 0; i < arr.Length; i++) {
if (arr[i] == bucket1) {
count1++;
}
if (arr[i] == bucket2) {
count2++;
}
}
if (count1 == 1) return bucket1;
return bucket2;
}
// return a number with the lowest bit of x^s set to 1 and rest 0.
// i.e. the lowest bit position where x and s differ.
int diff(int x, int s) {
return lowestBit(x^s);
}
// Returns a number with only the lowest bit of y set.
int lowestBit(int y) {
return y & ~(y-1);
}
La idea es la siguiente:
que dicen los números que aparecen una vez que son a, b, c.
Ahora ejecute el XOR a través de la matriz para obtener s = a XOR b XOR c.
Dado que los números son distintos, observe que s no puede ser ni a ni boc (ya que los otros dos serán iguales en ese momento), por lo que hay al menos un bit (no necesariamente en la misma posición), donde cada de a, b, c difiere de s.
En el caso de los dos números, pudimos ver que s es distinto de cero y elegimos un bit que diferenciaba un & b y trabajamos con eso.
Nos encontramos con dificultades cuando tenemos tres números, pero aún podemos encontrar un poco para diferenciar uno de los números.
Para cada número x, encuentre el bit más bajo que difiera de s. Considere el número binario en el que solo ese bit se establece en uno y el resto es cero. Llame a este número diff (x).
Ahora si calculamos diff (x) para cada número y XOR juntos, obtenemos d = diff (a) XOR diff (b) XOR diff (c).
Observe que d no puede ser cero.
Ahora encuentre el bit más bajo de d. Esta posición de bit se puede usar para dividir uno de a, b, c, ya que no todos a, b, c pueden tener el mismo bit en esa posición: si lo hicieron, entonces ese bit de s que es el XOR de aquellos tres deben ser iguales, pero nos aseguramos de que elegimos ese bit de s para que difiera de al menos uno de los bits correspondientes en a, b, c.
Volvemos a XOR, diferenciando en este bit, y verificando cuál de los dos números resultantes aparece exactamente una vez en la matriz. Una vez que encontramos un número, sabemos cómo lidiar con dos números.
Para encontrar el diff solo use el bithack: x & ~(x-1), que es un bit-hack estándar y puede considerarse O (1) (en lugar de O (número de bits)).
Pregunta esotérica + sin propósito útil = ¿deberes? –
@Robert Harvey - Podría ser una pregunta de Project Euler –
¿Cuántas pases sobre los datos está permitido? De lo contrario, parecería que hay una solución O (n^2) trivial que usa igualdad (el operador de igualdad es bitwise). – Akusete