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

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

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

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

Ответы

Ответ 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 этих двух групп, начиная с бит я + 1.
    • Если группа 10 и группа 01 непусты, рекурсивно найдите максимальный XOR этих двух групп, начиная с бит я + 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).

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

Ответ 2

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

0x100000
0x100ABC
0x001ABC
0x000ABC

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

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

Ответ 3

Это можно решить с помощью O(NlogN) временной сложности, используя Trie.

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

Для элементов 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;
}

Ответ 4

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

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

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

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

Ответ 5

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

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

Ответ 6

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