Два элемента в массиве, xor которых максимальный

Question

Учитывая массив целых чисел, вам нужно найти два элемента, XOR которых максимален.

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

Кроме этого, есть ли эффективный алгоритм?

Answer 1

Я думаю, что для этого есть алгоритм 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
• чисел, начиная с 10
• чисел, начиная с 01
• чисел, начиная с 00

Если в группе 11 и 00 или в группах 10 и 01 есть любые номера, их XOR будет идеальным (начиная с 11). Следовательно, если любая из этих пар групп не пуста, рекурсивно вычислить идеальное решение из этих групп, тогда вернем максимум этих подзадач. В противном случае, если обе группы пусты, это означает, что все цифры должны иметь одну и ту же цифру во второй позиции. Следовательно, оптимальный XOR числа, начинающегося с 1, и числа, начинающегося с 0, закончится тем, что следующий второй бит будет отменен, поэтому мы должны просто посмотреть на третий бит.

Это дает следующий рекурсивный алгоритм, который, начиная с двух групп чисел распределяли их MSB, дает ответ:

• Учитывая группы 1 и группы 0 и бит индекса I:
  • Если индекс бит равен количеству бит, верните XOR (уникальное) число в 1 группе и (уникальный) номер в группе 0.
  • Создайте группы групп 11, 10, 01 и 00 из этих групп.
  • Если группа 11 и группа 00 непусты, рекурсивно найдите максимальный XOR этих двух групп, начиная с бит i + 1.
  • Если группа 10 и группа 01 непусты, рекурсивно найдите максимальный XOR этих двух групп, начиная с бит i + 1.
  • Если возможно одно из указанных выше пар, верните максимальную пару, найденную рекурсией.
  • В противном случае, все номера должны иметь один и тот же бит в позиции I, поэтому вернуть максимальную пару найти, посмотрев на биту я + 1 на группы 1 и 0.

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

Надеюсь, это поможет! Это была потрясающая проблема!

Answer 2

Игнорирование знакового бита, одно из значений должно быть одним из значений с самым высоким значащим битом. Если все значения не имеют этого бита, в этом случае вы переходите к следующему старшему значащему биту, который не задан во всех значениях. Таким образом, вы можете оценить возможности для 1-го значения, посмотрев на HSB. Например, если имеются возможности

0x100000 
0x100ABC 
0x001ABC 
0x000ABC 

Первое значение максимальной пары должно быть либо 0x100000, либо 0x10ABCD.

@ Внутренний сервер Ошибка. Я не думаю, что наименьшее обязательно правильно. У меня нет отличной идеи для сравнения второго значения. Просто любое значение, которое не является в списке возможных 1-ых значений. В моем примере 0x001ABC или 0x000ABC.

Answer 3

Сделать рекурсивную функцию, которая принимает в качестве аргументов два списка целых чисел A и B. В качестве возвращаемого значения возвращается два целых числа: один из A и один из B, которые максимизируют XOR этих двух. Если все целые числа равны 0, верните (0,0). В противном случае функция выполняет некоторую обработку и вызывает себя рекурсивно дважды, но с меньшими целыми числами. В одном из рекурсивных вызовов он рассматривает взятие целого числа из списка A, чтобы предоставить 1 бит k, а в другом вызове он считает, взяв целое число из списка B, чтобы предоставить от 1 до бит k.

У меня нет времени на вступление, но может быть, этого будет достаточно, чтобы увидеть ответ? Кроме того, я не уверен, будет ли время работы лучше, чем N^2, но это, вероятно, будет.

Answer 4

Очень интересная проблема! Вот моя идея:

• Сначала построить бинарное дерево из всех чисел, с использованием двоичного представления и сортировать их в дерево наиболее значимые бит первый (добавить ведущие нули, чтобы соответствовать самому длинному числу). По завершении каждого пути от корня до любого листа представляет собой один номер от оригинала .
• Пусть a и b являются указателями на узел дерева и инициализируют их в корне.
• Теперь переместите a и b вниз по дереву, пытаясь использовать противоположные ребра на каждом шаге, т. Е. Если a движется вниз по краю 0, b перемещается вниз по 1-краю, если это невозможно.

Если a и b достигают листа, то должны указывать на два числа с «очень маленькими» одинаковыми битами.

Я только что сделал этот алгоритм и не знаю, правильно ли это или как его доказать. Однако это должно быть в O (n) время работы.

Answer 5

Мы можем найти максимальное число в O (n) времени, а затем цикл через массив, выполняющий xor с каждым элементом. Предполагая, что стоимость операции xor равна O (1), мы можем найти max xor двух чисел в O (n) времени.

Answer 6

Это может быть решена в O(NlogN) временной сложности с использованием Trie.

• Построить три. Для каждого целочисленного ключа каждый узел trie будет удерживать каждый бит (0 или 1), начиная с самого значащего бита.
• Теперь для каждого arr[i] элемента arr[0, 1, ..... N]
  • Выполните запрос, чтобы получить максимальное значение XOR возможное для arr[i]. Мы знаем, что xor бит разного типа (0^1 или 1^0) всегда 1. Поэтому во время запроса для каждого бита попытайтесь пересечь узел, удерживающий противоположный бит. Это приведет к тому, что этот бит 1 приведет к максимизации значения xor. Если нет узла с противоположным битом, только затем перейдите к одному и тому же битовому узлу.
  • После запроса введите arr[i] в состав.
  • Для каждого элемента отслеживайте максимально возможное значение Xor.
  • Во время ходьбы по каждому узлу создайте другой ключ, для которого максимизируется Xor.

Для N элементов, нам нужно один запрос (O(logN)) и одну вставку (O(logN)) для каждого элемента. Таким образом, общая временная сложность составляет O(NlogN).

Вы можете найти красивое иллюстрированное объяснение того, как это работает in this thread.

Вот C++ реализация выше алгоритма:

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; 
}