Solution by apletea


  • 1
    A

    Solution

    Approach #1 Brute force

    it's takes O(n^2) time and O(1) space complexity.

    Java

    public class Solution {
        public int findMaximumXOR(int[] nums) {
            int ans = Integer.MIN_VALUE;
            if (nums.length == 1)
                return 0;
            for (int i = nums.length-1; i >=0; --i){
                for (int j = i-1; j>=0;--j){
                    ans = Math.max(ans,nums[i]^nums[j]);
                }
            }
            return ans;
        }
    }
    

    Approach #2 TreeNode

    It's takes O(n) time and O(2^32) space complexity.
    The idea is the construct from binary numbers representation binary tree and after this iterate through this tree by each number.

    C++

    class Solution {
    public:
        class TreeNode {
        public:
            TreeNode* next[2];
            TreeNode () {memset(next,NULL, 2*sizeof(TreeNode*));};
        };
        TreeNode* buildTree(vector<int>& nums) {
            TreeNode* root = new TreeNode(), *cur;
            int n = nums.size();
            for (int i = 0; i < n; ++i) {
                int num = nums[i];
                cur = root;
                for (int j = 31; j >= 0; --j) {
                    int index = ((num >> j) & 1);
                    if (!cur->next[index])
                        cur->next[index] = new TreeNode();
                    cur = cur->next[index];
                }
            }
            return root;
        }
    
        int   helper(TreeNode* cur, int num) {
            int res = 0;
            for (int i = 31; i >= 0; --i) {
                int index = ((num >> i) & 1) ? 0 : 1;
                res <<= 1;
                if (cur->next[index]) {
                    res |= 1;
                    cur = cur->next[index];
                } else {
                    res |= 0;
                    cur = cur->next[index ? 0 : 1];
                }
            }
            return res;
        }
    
        int findMaximumXOR(vector<int>& nums) {
            int res = 0;
            TreeNode* root = buildTree(nums);
    
            for (auto & num : nums) {
                res = max(res, helper(root, num));
            }
    
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.