Найти три цифры получилось только один раз


В последовательности длины n, где n=2k+3, то есть есть k уникальных чисел, появляющихся дважды и три цифры появились только один раз.

Вопрос в следующем: Как найти три уникальных числа, которые появились только один раз?

Например, в последовательности 1 1 2 6 3 6 5 7 7 три уникальных числа равны 2 3 5.

Примечание: 3

Ограничения памяти: 1000КБ, это означает, что мы не можем хранить все последовательность.

Метод, который я пробовал(превышение предела памяти):

Я инициализирую дерево, и при чтении в одном числе я пытаюсь удалить его из дерева, если remove возвращает false (не найден), я добавляю его в дерево. Наконец, дерево имеет три числа. Он работает, но является пределом памяти превышения.

Я знаю, как найти одно или два таких числа с помощью битовой манипуляции. Поэтому мне интересно, если

Мы можем найти три, используя один и тот же метод(или какой-то метод похожие)?

Метод поиска одного / двух чисел появился только один раз:

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

Если их два, мы можем сначала применить XOR к последовательности, а затем разделить последовательность на 2 разделите на один бит результат, равный 1, и снова примените XOR к 2 частям, и мы найдем ответ.

6 16

6 ответов:

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

Нам нужно два целых числа для каждого бита чисел (например, 32 бита). Для каждого числа, если этот бит равен нулю, XOR первое целое число с ним. Если это не так, XOR второе целое число с ним.

Кроме того, подсчитайте, сколько раз вы находите 1 или 0 в каждой позиции (нам нужно только проверить, является ли это четным или нечетным, поэтому сохраняйте логическое значение).

После итерации наши пары целых чисел будут одно из следующих. Первое число здесь представляет собой четное число, второе-нечетное.

0, a^b^c
a^b, c
a^c, b
b^c, a

Для каждой пары проверьте четное целое число. Если оно равно нулю, то мы знаем, что другое целое число-a^b^c, так как никакие два из наших результатов не будут равны. В противном случае мы нашли значение нечетного числа count integer.

public static int[] find3(int[] list) {
    int[][] xors = new int[32][2];
    boolean[] counts = new boolean[32];
    for (int curr : list) {
        for (int i = 0; i < 32; i++) {
            xors[i][(curr & (1 << i)) >> i] ^= curr;
            counts[i] ^= ((curr & (1 << i)) == (1 << i));
        }
    }

    // this really shouldn't take so many lines
    int[] ret = new int[3];
    int found = 0;
    for (int i = 0; i < 32; i++) {
        int oddCount = xors[i][counts[i] ? 1 : 0];
        int evenCount = xors[i][counts[i] ? 0 : 1];
        if (evenCount != 0) { // avoid the 0, a^b^c case.
            if (found == 0) {
                ret[0] = oddCount;// a
                ret[2] = evenCount;// b^c for now
                found++;
            } else if (found == 1 && ret[0] != oddCount) {
                ret[1] = oddCount;// b
                ret[2] ^= oddCount;// (b^c)^b == c
                break;
            }
        }
    }
    return ret;
}

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

Вы можете сделать это в 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);
}

Идея заключается в следующем:

Скажем, что числа, которые появляются один раз, являются а,б.

Теперь запустите исключающее или через массив получить s = исключающее ИЛИ исключающее ИЛИ с б.

Так как числа различны, заметьте, что s не может быть ни a, ни b, ни c (поскольку тогда два других будут равны), таким образом, существует по крайней мере один бит (не обязательно в одной и той же позиции), где каждый из a,b, c отличается от s.

В случае двух чисел мы могли бы увидеть, что s Не равно нулю, и выбрать бит, который дифференцировал a & b, и работать с ним.

Мы сталкиваемся с трудностями, когда у нас есть три числа, но мы все еще можем найти немного, чтобы отличить одно из чисел.

Для каждого числа x найдите наименьший бит, отличающийся от s. рассмотрим двоичное число, в котором только этот бит равен единице, а остальные равны нулю. Назовем это число diff (x).

Теперь, если мы вычисляем разность(х) для каждого номера и XOR их вместе, мы получим д = дифф(а) исключающее ИЛИ дифф(б) исключающее ИЛИ дифф(с).

Обратите внимание, что d не может быть нулем.

Теперь найдите наименьший бит набора d. Эта позиция бита может можно использовать для выделения одного из a,b,c, так как не все a,b,c могут иметь один и тот же бит в этой позиции: если они это сделали, то тот бит s, который является XOR этих трех,должен быть одинаковым,но мы убедились, что мы выбрали этот бит s, чтобы отличаться по крайней мере от одного из соответствующих битов в a, b, c.

Итак, мы снова XOR, дифференцируясь по этому биту, и проверяем, какое из двух результирующих чисел появляется ровно один раз в массиве. Как только мы находим одно число, мы знаем, как справиться с двумя числа.

Чтобы найти разницу, просто используйте битхак: x & ~(x-1), который является стандартным бит-Хак и может рассматриваться как O(1) (вместо O(количество битов)).

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

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

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

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

  • флип 2-й бит
  • перевернуть 6-й бит
  • флип 3-й бит
  • перевернуть 6-й бит
  • etc
Затем, когда вы закончите просматривать список, вы можете прочитать биты, чтобы найти три уникальных числа. Все они будут представлены битами '1', а остальные числа будут представлены 0s.

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


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

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

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

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

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

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

Создайте два фильтра Bloom. Первый (А) содержит числа, которые были найдены по крайней мере один, а второй (Б) содержит числа, которые были найдены дважды.

Псевдокод:

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

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

Задача становится все сложнее и сложнее по мере добавления новых уникальных значений, главным образом потому,что вы можете выбрать 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

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

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