Leetcode 421. Maximum XOR of Two Numbers in an Array

Tyan

发布于 2019-05-25 22:19:34

2960

发布于 2019-05-25 22:19:34

文章被收录于专栏：SnailTyanSnailTyan

文章作者：Tyan

博客：noahsnail.com | CSDN | 简书

1. Description

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;
    }
};