Два элемента в массиве с максимальным значением xor

Question

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

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

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

Answer 1

Я думаю, что для этого у меня есть алгоритм O (n lg U), где U - наибольшее число.Идея похожа на user949300, но с более подробной информацией.

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

Это можно решить за O(NlogN) сложность времени, используя 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).

. Вы можете найти хорошее наглядное объяснение того, как это работает в этой теме .

Вот реализация 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;
}

Answer 3

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

0x100000
0x100ABC
0x001ABC
0x000ABC

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

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

Answer 4

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

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

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

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

Answer 5

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

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

Answer 6

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