Найти три числа появились только один раз

Ответ 1

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

Нам нужны два целых числа для каждого бита чисел (например, 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;
}

Ответ 2

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

Вы можете сделать это в 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, дифференцируем на этом бите и проверяем, какое из двух результирующих чисел появляется ровно один раз в массиве. Как только мы найдем одно число, мы знаем, как иметь дело с двумя числами.

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

Ответ 3

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

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

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

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

• flip 2-й бит
• flip 6-й бит
• flip 3-й бит
• flip 6-й бит
• и т.д.

Затем, как только вы закончите перебирать список, вы можете прочитать бит, чтобы найти три уникальных номера. Все они будут представлены "1" битами, а остальные числа будут представлены 0s.

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

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

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

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

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

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

• Пусть L обозначает исходный список, а C обозначает его копию.
• Удалите все дубликаты из C (существует множество способов сделать это эффективно).
• Создайте хэш-таблицу H и для каждого элемента в C вставьте пару ключ/значение < number, pos > в H, где number - текущий элемент в C, а pos - его положение в C. Итак, учитывая число, которое появляется в L, мы можем теперь использовать H, чтобы найти это число в C.
• Выделите количество бит, равное размеру C, и инициализируйте эти биты до 0.
• Траверс L. Каждый раз, когда мы запускаем accross number, получаем его значение от H и переворачиваем этот бит в нашем списке бит.
• Переместите список бит - для каждого "1" бита, получите номер от C, который находится в этой позиции, - это один из уникальных номеров.

Ответ 4

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

Создайте два фильтра Bloom. Первый (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 КБ, вероятность ошибки будет смехотворно низкой.

Ответ 5

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

Вы можете сделать 3 значения в постоянном пространстве и время O (n * k), где k - количество бит в наибольшем целое. (So ​​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

Ответ 6

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

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