Учитывая массив целых чисел, вам нужно найти два элемента, XOR которых максимален.
Существует наивный подход - просто, выбирая каждый элемент и xoring с другими элементами, а затем сравнивая результаты, чтобы найти пару.
Кроме этого, есть ли эффективный алгоритм?
Я думаю, что для этого есть алгоритм O (n lg U), где U - наибольшее число. Идея похожа на user949300, но немного более подробно.
Интуиция такова. Когда вы XORing два числа вместе, чтобы получить максимальное значение, вы хотите иметь 1 в наивысшей возможной позиции, а затем пар, которые имеют 1 в этой позиции, вы хотите, чтобы соединение с 1 на следующем возможно наивысшее положение и т.д.
Итак, алгоритм выглядит следующим образом. Начните с нахождения наивысшего 1 бита в любом месте чисел (вы можете сделать это вовремя O (n lg U), выполнив O (lg U) для каждого из n чисел). Теперь разделим массив на две части - одно из чисел, у которых есть 1 в этом бите и группа с 0 в этом бите. Любое оптимальное решение должно сочетать число с 1 в первом месте с числом с 0 в этом месте, так как это поставит 1 бит как можно выше. У любого другого спаривания есть 0.
Теперь, рекурсивно, мы хотим найти спаривание чисел из 1 и 0 группы с наивысшим значением 1 в них. Чтобы сделать это, из этих двух групп разделили их на четыре группы:
Если есть числа в группе 11 и 00 или в группах 10 и 01, их XOR будет идеальным (начиная с 11). Следовательно, если любая из этих пар групп не пуста, рекурсивно вычислить идеальное решение из этих групп, тогда вернем максимум этих подзадач. В противном случае, если обе группы пусты, это означает, что все цифры должны иметь одну и ту же цифру во второй позиции. Следовательно, оптимальный XOR числа, начинающегося с 1 и числа, начинающегося с 0, закончится тем, что следующий второй бит будет отменен, поэтому мы должны просто посмотреть на третий бит.
Это дает следующий рекурсивный алгоритм, который, начиная с двух групп чисел, разделенных их MSB, дает ответ:
Чтобы начать алгоритм, вы можете просто разбивать числа из исходной группы на две группы - цифры с MSB 1 и номерами с MSB 0. Затем вы удаляете рекурсивный вызов вышеуказанного алгоритма с двумя группами числа.
В качестве примера рассмотрим числа 5 1 4 3 0 2. Они имеют представления
101 001 100 011 000 010
Начнем с разбиения их на 1 группу и группу 0:
101 100
001 011 000 010
Теперь применим приведенный выше алгоритм. Мы разделили это на группы 11, 10, 01 и 00:
11:
10: 101 100
01: 011 010
00: 000 001
Теперь мы не можем спаривать любые 11 элементов с 00 элементами, поэтому мы просто возвращаемся к группам 10 и 01. Это означает, что мы создаем группы 100, 101, 010 и 011:
101: 101
100: 100
011: 011
010: 010
Теперь, когда мы попадаем в ведра с одним элементом в них, мы можем просто проверить пары 101 и 010 (что дает 111) и 100 и 011 (что дает 111). Любой из этих вариантов работает здесь, поэтому мы получаем, что оптимальный ответ равен 7.
Подумайте о времени работы этого алгоритма. Обратите внимание, что максимальная глубина рекурсии равна O (lg U), так как в номерах есть только O (log U). На каждом уровне дерева каждое число отображается ровно с одним рекурсивным вызовом, и каждый из рекурсивных вызовов работает пропорционально общему числу чисел в группах 0 и 1, потому что мы должны распределять их по их битам. Следовательно, в дереве рекурсии есть уровни O (log U), и каждый уровень O (n) работает, давая полную работу O (n log U).
Надеюсь, это поможет! Это была потрясающая проблема!
Игнорируя бит знака, одно из значений должно быть одним из значений с наибольшим значащим битом. Если все значения не имеют установленного бита, в этом случае вы переходите к следующему самому высокому значащему биту, который не задан во всех значениях. Таким образом, вы можете оценить возможности для 1-го значения, посмотрев на HSB. Например, если возможности
0x100000
0x100ABC
0x001ABC
0x000ABC
Первое значение пары max должно быть либо 0x100000, либо 0x10ABCD.
@Внутренняя ошибка сервера Я не думаю, что наименьшее обязательно правильно. У меня нет отличной идеи для сравнения второго значения. Просто любое значение, которое не входит в список возможных 1-го значения. В моем примере 0x001ABC или 0x000ABC.
Это можно решить с помощью O(NlogN) временной сложности, используя Trie.
arr[i] arr[0, 1, ..... N]
arr[i]. Мы знаем, что xor битов разных типов (0 ^ 1 или 1 ^ 0) всегда 1. Поэтому во время запроса для каждого бита попробуйте пройти node, удерживая противоположный бит. Это приведет к тому, что этот бит 1 приведет к максимизации значения xor. Если нет node с противоположным битом, только затем пройдите тот же бит node.arr[i] в trie.Для элементов N нам нужен один запрос (O(logN)) и одна вставка (O(logN)) для каждого элемента. Таким образом, общая временная сложность O(NlogN).
Вы можете найти красивое иллюстрированное объяснение того, как оно работает в этом потоке.
Ниже приведена реализация С++ алгоритма:
const static int SIZE = 2;
const static int MSB = 30;
class trie {
private:
struct trieNode {
trieNode* children[SIZE];
trieNode() {
for(int i = 0; i < SIZE; ++i) {
children[i] = nullptr;
}
}
~trieNode() {
for(int i = 0; i < SIZE; ++i) {
delete children[i];
children[i] = nullptr;
}
}
};
trieNode* root;
public:
trie(): root(new trieNode()) {
}
~trie() {
delete root;
root = nullptr;
}
void insert(int key) {
trieNode* pCrawl = root;
for(int i = MSB; i >= 0; --i) {
bool bit = (bool)(key & (1 << i));
if(!pCrawl->children[bit]) {
pCrawl->children[bit] = new trieNode();
}
pCrawl = pCrawl->children[bit];
}
}
int query(int key, int& otherKey) {
int Xor = 0;
trieNode *pCrawl = root;
for(int i = MSB; i >= 0; --i) {
bool bit = (bool)(key & (1 << i));
if(pCrawl->children[!bit]) {
pCrawl = pCrawl->children[!bit];
Xor |= (1 << i);
if(!bit) {
otherKey |= (1 << i);
} else {
otherKey &= ~(1 << i);
}
} else {
if(bit) {
otherKey |= (1 << i);
} else {
otherKey &= ~(1 << i);
}
pCrawl = pCrawl->children[bit];
}
}
return Xor;
}
};
pair<int, int> findMaximumXorElements(vector<int>& arr) {
int n = arr.size();
int maxXor = 0;
pair<int, int> result;
if(n < 2) return result;
trie* Trie = new trie();
Trie->insert(0); // insert 0 initially otherwise first query won't find node to traverse
for(int i = 0; i < n; i++) {
int elem = 0;
int curr = Trie->query(arr[i], elem);
if(curr > maxXor) {
maxXor = curr;
result = {arr[i], elem};
}
Trie->insert(arr[i]);
}
delete Trie;
return result;
}
Очень интересная проблема! Вот моя идея:
Если a и b достигают листа, то должны указывать на два числа с "очень маленькими" одинаковыми битами.
Я только что сделал этот алгоритм и не знаю, правильно ли это или как его доказать. Однако это должно быть в O (n) время выполнения.
Сделайте рекурсивную функцию, которая в качестве аргументов принимает два списка целых чисел A и B. В качестве возвращаемого значения возвращается два целых числа: один из A и один из B, которые максимизируют XOR этих двух. Если все целые числа равны 0, верните (0,0). В противном случае функция выполняет некоторую обработку и вызывает себя рекурсивно дважды, но с меньшими целыми числами. В одном из рекурсивных вызовов он рассматривает выбор целочисленного числа из списка A для подачи 1 бит k, а в другом вызове он рассматривает выбор целочисленного числа из списка B для подачи от 1 до бит k.
У меня нет времени, чтобы заполнить детали, но, возможно, этого будет достаточно, чтобы увидеть ответ? Кроме того, я не уверен, будет ли время работы лучше, чем N ^ 2, но оно, вероятно, будет.
Мы можем найти максимальное число в O (n) времени, а затем цикл через массив, выполняющий xor с каждым элементом. Предполагая, что стоимость операции xor равна O (1), мы можем найти max xor двух чисел в O (n) времени.