题目描述

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.
Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

算法1

(Trie树) $O(n)$

C++ 代码

class Solution {
struct treenode {
    treenode* left, *right;
    treenode():left(NULL), right(NULL) {} 
};
public:
    int findMaximumXOR(vector<int>& nums) {
        treenode* root = new treenode();
        int ans = 0;
        // build a trie and get the max xor value on the fly for the current trie
        for (int num:nums)  ans = max(ans, build(root, num));
        return ans;
    }
private:
    int build(treenode* p, int num) {
        int ans = 0, mask = 1<<30;
        treenode* q = p;
        for (int i = 30; i >= 0; i--) {
            ans <<= 1;
            if (num&mask) {
                //build a trie
                if (p->right == NULL)  p->right = new treenode();
                p = p->right;
                //get xor value on the fly
                if (q->left) {
                    ans++;
                    q = q->left;
                }
                else 
                    q = q->right;
            }
            else {
                if (p->left == NULL)  p->left = new treenode();
                p = p->left;
                if (q->right) {
                    ans++;
                    q = q->right;
                }
                else 
                    q = q->left;
            }
            mask >>= 1;
        }
        return ans;
    }
};

Python 版
从最高位构造到最低位 add a ‘1’ to every bit 每一位加1

def findMaximumXOR(self, nums):
    answer = 0
    for i in range(32)[::-1]:
        answer <<= 1
        prefixes = {num >> i for num in nums}
        answer += any(answer^1 ^ p in prefixes for p in prefixes)
    return answer

answer^1 ^ p 作用：
1. find the two elements in nums that constructs the previous answer找到nums数组里构建上一个ans的两个数
2. check this two elements have opposite bits at current position 比较这两个数看他在当前坐标下有不同的位

更容易读版本： next candidate = current answer <<1 + 1.

def findMaximumXOR(self, nums):
        ans = 0
        for i in reversed(range(32)):
            prefixes = set([x >> i for x in nums])
            ans <<=1
            candidate = ans + 1
            for p in prefixes:
                if candidate ^ p in prefixes:
                    ans = candidate
                    break      
        return ans

c++版同python逻辑

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int ret=0;
        if(nums.size()==0) return 0;
        else if(nums.size()==1) return 0;
        unordered_set<int> tmp;

        for(int i=31;i>=0;i--){
            ret = (ret<<1) | 1;
            tmp.clear();
            for(auto &nn:nums) {
                tmp.insert(nn>>i);
            }
            bool found=false;
            for(auto &tt:tmp) {
                if(tmp.count(tt^ret)>0) {
                    found=true;
                    break;
                }
            }
            if(!found) ret-=1;
        }
        return ret;
    }
};