两数最大异或值

C++ 解法, 执行用时: 13ms, 内存消耗: 2108KB, 提交时间: 2022-04-17

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型
     */
    int son[300010][2],idx=0;
    void insert(int x)
    {
        int p=0;
        for(int i=30;i>=0;i--)
        {
            int u = x>>i&1;
            if(son[p][u]==0)
            {
                son[p][u]=++idx;
            }
            p=son[p][u];
        }
    }
    int query(int x)
    {
        int p=0,res=0;
        for(int i=30;i>=0;i--)
        {
            int u = x>>i&1;
            if(son[p][!u])
            {
                res+=1<<i;
                p=son[p][!u];
            }
            else
            {
                p=son[p][u];
            }
        }
        return res;
    }
    int maxXOR(vector<int>& array) {
        // write code here
        int ans=0;
        for(int num:array)
        {
            insert(num);
        }
        for(int num:array)
        {
            ans=max(ans,query(num));
        }
        return ans;
        
    }
};

C++ 解法, 执行用时: 20ms, 内存消耗: 788KB, 提交时间: 2022-04-07

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型
     */
    int maxXOR(vector<int>& array) {
        // write code here
        int s=0,ki;
        for(int i=0;i<array.size()-1;i++){
            for(int j=i+1;j<array.size();j++){
                ki=array[i]^array[j];
                if(ki>s)s=ki;
            }
        }
        return s;
    }
};

C 解法, 执行用时: 61ms, 内存消耗: 816KB, 提交时间: 2022-03-30

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param array int整型一维数组 
 * @param arrayLen int array数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int maxXOR(int* array, int arrayLen ) {
    // write code here
    int max = 0;
    int tmp = 0;
    for (int i = 0; i < array - 1; ++i) {
        for (int j = i + 1; j < arrayLen; ++j) {
            tmp = array[i] ^ array[j];
            max = max > tmp ? max : tmp;
        }
    }
    return max;
        
}

C++ 解法, 执行用时: 62ms, 内存消耗: 5544KB, 提交时间: 2022-06-28

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param array int整型vector
     * @return int整型
     */
    int maxXOR(vector<int>& array) {
        // write code here
        int maxNum = array[0];
        for (int num : array) {
            maxNum = max(maxNum, num);
        }
        
        if (maxNum == 0) {
            return 0;
        }
        
        int L = (sizeof(int) << 3) - __builtin_clz(maxNum) - 1;
        int maxXor = 0;
        
        for (int k = L; k >= 0; --k) {
            unordered_set<int> seen;
            int curXor = (maxXor <<= 1) | 1;
            for (int& num : array) {
                if (seen.count(curXor ^ (num >> k))) {
                    maxXor = curXor;
                    break;
                }
                seen.insert(num >> k);
            }
        }

        return maxXor;
    }
};

C++ 解法, 执行用时: 79ms, 内存消耗: 14376KB, 提交时间: 2022-06-06

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型
     */
    int son[10000010][2],idx=0;
    void my_insert(int x)
    {
        int p=0;
        for(int i=30;i>=0;i--)
        {
            int u=(x>>i)&1;
            if(!son[p][u])son[p][u]=++idx;
            p=son[p][u];
        }
    }
    int query(int x)
    {
        int res=0;
        int p=0;
        for(int i=30;i>=0;i--)
        {
            int u=(x>>i)&1;
            if(son[p][!u]){
                res+=(1<<i);
                p=son[p][!u];
            }
            else{
                p=son[p][u];
            }
        }
        return res;
    }
    int maxXOR(vector<int>& array) {
        // write code here
        int maxn=0;
        for(int i=0;i<array.size();i++)
        {
            my_insert(array[i]);
        }
        for(int i=0;i<array.size();i++)
        {
            maxn=max(maxn,query(array[i]));
        }
        return maxn;
    }
};

详情