Leetcode 421. Maximum XOR of Two Numbers in an Array

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

Maximum XOR of Two Numbers in an Array

2. Solution

• Version 1

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int max = 0;
        int current = 0;
        for(int i = 0; i < nums.size(); i++) {
            for(int j = i + 1; j < nums.size(); j++) {
                current = nums[i] ^ nums[j];
                if(current > max) {
                    max = current;
                }
            }
        }
        return max;
    }
};

• Version 2

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int max = 0;
        int mask = 0;
        unordered_set<int> s;
        for(int i = 30; i >= 0; i--) {
            mask = mask | (1 << i);
            for(int value : nums) {
                s.insert(mask & value);
            }
            int candidate = max | (1 << i);
            for(int value : s) {
                if(s.count(candidate ^ value)) {
                    max = candidate;
                    break;
                }
            }
            s.clear();
        }
        return max;
    }
};

Reference

1. https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/description/