Поиск пар с наименьшими значениями XOR из списка

Я работаю над проблемой, в которой я, как ожидается, возьму все пары целых чисел в массиве, а затем найти K наименьший целые числа, полученные от xor'ing. Размер массива может быть равен N = 100000 и поэтому K может быть довольно большим, но его ограничено до 250000.

Например, если N = 5 и K = 4,

наш массив {1 3 2 4 2}

Цифры, полученные в результате xoring (1 и 3, 1-2, 1-4, 1-2, 3-2, 3-4, 3-2 и т.д.)

3 3 2 5 0 1 6 1 6 7

Так как K = 4, мы должны напечатать 4 наименьших целых числа. поэтому ответ будет 0 1 1 2.

Поскольку срок составляет 2 секунды и очень плотный, используя подход грубой силы xoring все числа будут тайм-аут. Мой подход был неправильным, и мне нужно Помогите. Возможно, мы сможем использовать лимит на K = 250000 и хотим знать, можно получить наименьшие числа K, не xoring все целые числа.

3 ответа

(x ^ y) == (x | y) - (x & y) >= |y - x|

Сортировка ваших номеров по порядку будет началом, потому что разница между парами даст вам нижнюю границу для xor и, следовательно, точку отсечки для того, чтобы прекратить поиск чисел до xor x с.

Существует также ярлык для поиска пар чисел, xor которых меньше (скажем) мощности 2, потому что вас интересует только x <= y <=x | (2 ^ N - 1). Если это не даст вам достаточно пар, увеличьте N и повторите попытку.

EDIT: вы можете, конечно, исключить пары чисел, которые вы уже нашли, xor которых меньше предыдущей степени 2, используя x | (2 & bull; (N - 1) - 1) y <= x | (2 ^ N) - 1.

Пример, основанный на (отсортированный) [1, 2, 2, 3, 4]

Начните с поиска пар чисел, xor которых меньше 1: для каждого числа x, ищите последующие числа y = x. Это дает {2, 2}.

Если вам нужно больше одной пары, найдите пары чисел, xor которых меньше 2, но не менее 1: для каждого числа x, поиск чисел x < y <=x | 1. Это дает {2, 3} (дважды).

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

Если вам нужно больше, найдите пары чисел, xor которых меньше 4, но не менее 2: для каждого числа x, для поиска чисел x | 1 < y <=x | 3. Это дает {1, 2} (дважды); {1, 3}.

Если вам нужно больше, найдите пары чисел, xor которых меньше 8, но не менее 4: для каждого числа x, поиск чисел x | 3 < y <=x | 7. Это дает {1, 4}; {2, 4} (дважды); {3, 4}.


Обратите внимание, что если все биты слева от bit n (считая справа) чисел x и y равны, x xor y ≤ 2 n -1

x = 0000000000100110
y = 0000000000110010
 ^Everything to the left of bit 5 is equal
 so x xor y ≤ 2<sup>5</sup>-1 = 31

Это можно использовать, сохраняя каждое число в побитовое-три - то есть, trie, где каждое ребро является либо 0 или 1. Тогда x xor y ≤ 2 d (x, y) -1, где d(x,y) - это число шагов, которые нам нужно переместиться, чтобы найти наименее общего предка x и y.

root
 (left-most bit)
 0
 /
 0
 /
 ...
 1
 / \
 0 1
 / /
 0 0
 ... ...
 / /
 0 0
 x y
x and y share an ancestor-node that is 5 levels up, so d(x,y) is 5

Как только у вас есть trie, легко найти все пары, чтобы d(x,y) = 1 - просто перейти ко всем уровням узлов 1 над листьями и сравнить каждого из этих детей node друг с другом. Эти значения дадут вам max x xor y из 2 1 -1 = 1.

Если у вас по-прежнему нет значений k, а затем перейдите к всем узлам уровня 2 над листьями и сравните каждого из этих внуков node друг с другом . Эти значения дадут вам max x xor y из 2 2 -1 = 3.

(На самом деле вам нужно только сравнить каждую из листьев в левом поддереве с каждым из листьев в правом поддереве, так как каждый из листьев в заданном поддереве уже были сопоставлены друг с другом)

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

Когда k мал (< lt; n 2), этот алгоритм O (n). Для больших k это O (2 b n), где b - количество бит на целое число (при условии, что нет много дубликатов).


Я бы подошел к этому, сначала отсортировав входной массив целых чисел. Тогда пары с наименьшими значениями xor будут рядом друг с другом (но не все соседние пары будут иметь наименьшие значения xor). Вы можете начать с соседних пар, затем работать наружу, проверять пары (N, N + 2), (N, N + 3), пока не достигнете нужного вам списка наименьших результатов.

Для вашего массива образцов {1 3 2 4 2} отсортированный массив равен {1 2 2 3 4}, а попарные значения xor:

1 xor 2 = 3
2 xor 2 = 0
2 xor 3 = 1
3 xor 4 = 7

Для следующего шага

1 xor 2 = 3
2 xor 3 = 1
2 xor 4 = 6

и снова,

1 xor 3 = 2
2 xor 4 = 6

наконец,

1 xor 4 = 5

Эта идея не является полной, но вы должны иметь возможность использовать ее для создания полного решения.

licensed under cc by-sa 3.0 with attribution.