数组中的两个元素,其xor是最大的

Question

给定一个整数数组,您必须找到两个XOR最大的元素.

有天真的方法 - 只需挑选每个元素和xoring与其他元素,然后比较结果找到对.

除此之外,有没有有效的算法？

Answer 1

我想我有一个O(n lg U)算法,其中U是最大的数字.这个想法类似于user949300,但有更多细节.

直觉如下.当您将两个数字一起进行异或运算时,要获得最大值,您希望在最高位置获得1,然后在此位置具有1的配对,您希望在下一个位置配对1可能的最高位置等

所以算法如下.首先在数字中的任何地方找到最高的1位(你可以在时间O(n lg U)中通过对每个n个数字执行O(lg U)工作来执行此操作).现在,将数组拆分为两部分 - 其中一个数字在该位中为1,而在该位中为0.任何最佳解决方案必须将数字与第一个点中的1和该点中带有0的数字组合,因为这将使1位尽可能高.任何其他配对都有0.

现在,递归地,我们想要找到1和0组中具有最高1的数字的配对.为此,在这两组中,将它们分成四组:

• 数字从11开始
• 数字从10开始
• 数字从01开始
• 以00开头的数字

如果11和00组或10和01组中有任何数字,则它们的XOR将是理想的(从11开始).因此,如果这些组中的任何一组不为空,则递归地从这些组计算理想解,然后返回那些子问题解的最大值.否则,如果两个组都为空,则表示所有数字在其第二个位置必须具有相同的数字.因此,以1开头的数字和从0开始的数字的最佳XOR将最终使下一个第二位取消,所以我们应该只看第三位.

这给出了以下递归算法,从它们的MSB划分的两组数字开始,给出了答案:

• 给定组1和组0以及位索引i:
  • 如果位索引等于位数,则返回1组中(唯一)编号的XOR和0组中的(唯一)编号.
  • 从这些组中构造组11,10,01和00.
  • 如果组11和组00是非空的,则递归地找到从位i + 1开始的那两个组的最大XOR.
  • 如果组10和组01是非空的,则递归地找到这两个组的最大XOR,从位i + 1开始.
  • 如果上述任何一对都是可能的,则返回递归找到的最大对.
  • 否则,所有数字必须在位置i中具有相同的位,因此通过查看组1和0上的位i + 1返回找到的最大对.

要启动算法,您实际上只需将初始组中的数字划分为两组 - 具有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在时间复杂度上解决。

• 构建一个尝试。对于每个整数键，trie 的每个节点将保存从最高有效位开始的每一位（0 或 1）。
• 现在对于每个arr[i]元素arr[0, 1, ..... N]
  • 执行查询以检索 可能的最大异或值arr[i]。我们知道不同类型位（0 ^ 1或1 ^ 0）的异或总是1。所以在查询每一位时，尽量遍历持有相反位的节点。这将使该特定位1导致 xor 值最大化。如果没有相反位的节点，则只遍历同位节点。
  • 查询后，插入arr[i]到trie中。
  • 对于每个元素，跟踪可能的最大 Xor 值。
  • 在遍历每个节点期间，构建 Xor 最大化的另一个键。

对于N元素，我们需要为每个元素一个 query( O(logN)) 和一个 insert( 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

忽略符号位，其中一个值必须是设置了最高有效位的值之一。 除非所有值都设置了该位，否则您将转到未在所有值中设置的下一个最高有效位。因此，您可以通过查看 HSB 来减少第一个值的可能性。例如，如果可能性是

0x100000
0x100ABC
0x001ABC
0x000ABC

最大对的第一个值必须是 0x100000 或 0x10ABCD。

@内部服务器错误我认为最小的不一定正确。我没有减少第二个值的好主意。只是不在可能的第一个值列表中的任何值。在我的示例中，0x001ABC 或 0x000ABC。