Найдите, что три числа появились только однажды

Проблема становится все сложнее и сложнее по мере того, как вы добавляете больше уникальных значений, главным образом потому, что вы можете выбрать A, B, C так, чтобы A xor B xor C = 0. Становится все труднее и труднее определить, имеет ли подмножество значений та же контрольная сумма, потому что она содержит все уникальные значения, или потому что она пропустила значения, которые произошли с xor до 0.

Вы можете сделать 3 значения в постоянном пространстве и времени O (n * k), где k - количество битов в самом большом целом числе. (Итак, время O (n) для вашего типичного случая: 32-битные целые числа.)

Было бы интересно узнать, станет ли временная граница нелинейной по N по мере увеличения количества уникальных значений, а вам по-прежнему требуется постоянное пространство.

//Special check for 0, because otherwise we don't know A xor B xor C != A xor B
if items unique-contains 0 then
    return 0 ++ SubProblem2Unique(items - 0)
//Compute A xor B xor C
val x = fold xor items
//Try to find a split which separates A and B from C.
for i in 0..WORD_SIZE
    //see if the checksum splits
    val x1 = fold xor [e in items where e & (1<<i) == 0]
    val x2 = x xor x1
    if x1 == x or x2 == x then continue //ith bit was the same for A and B and C
    //C is either x1 or x2
    val C = if items unique-contains x1 then x1 else x2
    return C ++ SubProblem2Unique(items - C)

throw InvalidInput

Это классический вопрос - мне его задали всего несколько недель назад. Чтобы решить эту проблему, вы берете количество возможных различных чисел, которые могут появиться, и выделяете это количество бит.

Например, если числа в списке должны находиться в диапазоне от 1 до 20, вы выделяете 20 битов - по одному для каждого числа и инициализируете каждый бит как 0.

Затем вы просматриваете список. Каждый раз, когда вы видите число, переверните соответствующий бит.

Например: с вашим примерным списком из 2 6 3 6 5 7 7 мы могли бы выделить 7 бит (для 1 2 3 4 5 6 7). Затем, просматривая список, мы должны сделать следующее:

• перевернуть 2-й бит
• перевернуть 6-й бит
• перевернуть 3-й бит
• перевернуть 6-й бит
• и т. Д.

Затем, когда вы закончите Просматривая список, вы можете прочитать биты, чтобы найти три уникальных числа.Все они будут представлены битами «1», а остальные числа будут представлены нулями.

Вы читаете список дважды, что занимает 2n раз, то есть O (n).

Редактировать: Возможно, что границы не будут указаны. Таким образом, одно из решений - просто сначала прочитать список, чтобы самостоятельно определить границы - тогда это все еще O (n).

Однако одна проблема, которая может возникнуть, заключается в том, что список может быть очень маленьким, но есть некоторые очень большие числа, что фактически делает диапазон слишком большим. Например:

1, 99999999999999999, 1, 99999999999999999, 2, 3, 4

Решение этой проблемы потребует много памяти из-за большого числа, присутствующего в списке, потому что, даже если чисел очень мало, диапазон очень велик, и мы распределяем биты в соответствии с диапазоном.

Затем решение может быть скорректировано, чтобы дать новое решение, как показано ниже, с использованием хэш-таблицы (хотя я не уверен, разрешено ли это, учитывая условие проблемы «только битовые манипуляции»):

1. Пусть L ​​ обозначают исходный список, а C обозначают его копию.
2. Удалите все дубликаты из C (существует множество способов сделать это эффективно).
3. Создайте хеш-таблицу H и для каждого элемента в C вставьте пару ключ / значение < число , pos > в H , где число - текущий элемент в C , а pos - его позиция в C . Итак, учитывая число, которое появляется в L , теперь мы можем использовать H , чтобы найти позицию этого числа в C .
4. Выделите количество битов, равное размеру C , и инициализируйте эти биты равными 0.
5. Traverse L . Каждый раз, когда мы перебираем число, получаем его значение из H и меняем этот бит в нашем списке битов.
6. Просмотрите список битов - для каждого бита «1» получите номер из C , который находится в этой позиции - это одно из уникальных чисел.

Если вероятностного решения будет достаточно, вы можете использовать Фильтр Блума .

Создайте два фильтра Блума. Первый (A) содержит числа, которые были найдены хотя бы один, а второй (B) содержит числа, которые были найдены дважды.

Псевдокод:

A = empty
B = empty

foreach x in the list
  if x in A
    add x to B
  else
    add x to A

foreach x in the list
  if x in A
    if !(x in B)
      print x

Если вы используете полные 1000 КБ, то вероятность ошибки будет смехотворно низкой.

Для более общей версии этой задачи (без этих глупых ограничений):

Вы можете сделать это за O(n) времени и O(1) пространства без предположения каких-либо границ, или итерации над всеми битами, и используя только O(1) времени трюки манипуляции битами, такие как трюк XOR, который работал для двух пропущенных чисел.

Вот (псевдо)код для нахождения только одного из чисел:

// 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) для каждого числа и перемножим их вместе, то получим 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(количество бит)).

Почему бы не использовать хэшсет? - Если число уже существует, удалите из хэшсета - если число не существует, поместите в хэшсет Окончательный хэшсет содержит только уникальные номера. Время: O(n) Память:o(k), где k — число различных элементов.

При подходе с хэшсетом решение является масштабируемым и может быть использовано для определения любого количества уникальных элементов в любой заданной последовательности.