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

Question

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

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

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

числа, возникающие в результате операции Исключающее ИЛИ (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 и хотим знать, возможно ли получить 44 наименьших чисел без xoring всех целых чисел.

Answer 1

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

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

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

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

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

Start, ища пар чисел, исключающее меньше, чем 1: для каждого числа х, поиск для последующего чисел у = Икс. Это дает {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}.

Answer 2

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

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

Answer 3

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

 
x = 0000000000100110 
y = 0000000000110010 
       ^Everything to the left of bit 5 is equal 
       so x xor y ≤ 25-1 = 31 

Это может быть использовано при хранении каждый номер в bitwise-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 

После того как вы синтаксического дерева, легко найти все пары такие, что d(x,y) = 1 - просто перемещаться по всем узлам 1 уровень выше листьев, и сравнить каждый из детей этого узла друг с другом. Эти значения дадут вам максимум -1 = 1.

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

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

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

---

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