Для более общей версии этой проблемы (без этих глупых ограничений):
Вы можете сделать это за время O (n) и пространство O (1) без при условии каких-либо границ или итерация по всем битам, и используя только O (1) трюки манипуляции с битами времени, такие как трюк XOR, который работал для 2 пропущенных чисел.
Вот (псевдо) код, чтобы найти только одно из чисел:
// 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);
}
Идея заключается в следующем:
Скажите, что числа, которые появляются однажды, являются a, b, c.
Теперь запустите XOR через массив, чтобы получить s = a XOR b XOR c.
Поскольку числа различны, обратите внимание, что s не может быть либо a, либо b, либо c (так как остальные два будут равны), таким образом, существует по крайней мере один бит (не обязательно в одной и той же позиции), где каждый из a, b, c отличается от s.
В случае двух чисел мы могли видеть, что s ненулевой, и выбирать бит, который дифференцирует a & b и работать с этим.
Мы сталкиваемся с трудностями, когда у нас есть три числа, но мы все еще можем найти немного, чтобы отличить одно из чисел.
Для каждого числа x найдите младший бит, который отличается от s. Рассмотрим двоичное число, в котором только этот бит установлен в единицу, а остальные равны нулю. Назовите этот номер diff (x).
Теперь, если мы вычислим diff (x) для каждого числа и XOR их вместе, мы получим d = diff (a) XOR diff (b) XOR diff (c).
Обратите внимание, что d не может быть нулем.
Теперь найдите младший установленный бит d. Эта битовая позиция может использоваться для выгрузки одного из a, b, c, поскольку не все a, b, c могут иметь один и тот же бит в этой позиции: если они это сделали, то тот бит s, который является XOR этих три должны быть одинаковыми, но мы убедились, что мы выбрали этот бит s, чтобы он отличался по крайней мере от одного из соответствующих битов в a, b, c.
Итак, мы снова выполняем XOR, дифференцируя этот бит, и проверяем, какое из двух результирующих чисел появляется в массиве ровно один раз. Найдя одно число, мы знаем, как обращаться с двумя числами.
Чтобы найти разность, используйте битхак: x & ~(x-1), который является стандартным бит-хаком и может рассматриваться как O (1) (вместо O (количество бит)).