421. Maximum XOR of Two Numbers in an Array

题目描述和难度

题目描述：

给定一个非空数组，数组中元素为 a₀, a₁, a₂, … , a_n-1，其中 0 ≤ a_i < 2³¹。

找到 a_i 和a_j最大的异或 (XOR) 运算结果，其中0 ≤ i, j < n 。

你能在O(n)的时间解决这个问题吗？

示例:

输入: [3, 10, 5, 25, 2, 8]

输出: 28

解释: 最大的结果是 5 ^ 25 = 28.

题目难度：中等。
英文网址：421. Maximum XOR of Two Numbers in an Array 。
中文网址：421. 数组中两个数的最大异或值。

思路分析

求解关键：

参考解答

参考解答1：暴力解法，可以通过测试，但不推荐。

public class Solution {
    public int findMaximumXOR(int[] nums) {
        int len = nums.length;
        int res = 0;
        // i 到 len -2 就可以了
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                res = Math.max(res, nums[i] ^ nums[j]);
            }
        }
        return res;
    }
}

参考解答2：使用位运算，从高位到低位依次决定每个数位上是 1 还是 0。

import java.util.HashSet;
import java.util.Set;

public class Solution2 {

    public int findMaximumXOR(int[] nums) {
        int res = 0;
        int mask = 0;
        for (int i = 31; i >= 0; i--) {
            // 注意点1：注意保留前缀的方法，mask 是这样得来的
            // 用异或也是可以的 mask = mask ^ (1 << i);
            mask = mask | (1 << i);
            Set<Integer> set = new HashSet<>();
            for (int num : nums) {
                // 注意点2：这里使用 & ，保留前缀的意思（从高位到低位）
                set.add(num & mask);
            }

            // 这里先假定第 n 位为 1 ，前 n-1 位 res 为之前迭代求得
            int temp = res | (1 << i);
            for (Integer prefix : set) {
                // 利用性质 a ^ b = c ，则 a ^ c = b，且 b ^ c = a
                if (set.contains(prefix ^ temp)) {
                    res = temp;
                    break;
                }
            }
        }
        return res;
    }
}

参考解答3：使用字典树（Trie）。

public class Solution3 {

    // 参考资料：http://www.cnblogs.com/njufl/p/6403043.html

    private class TrieNode {
        private TrieNode[] next;

        public TrieNode() {
            next = new TrieNode[2];
        }
    }

    public int findMaximumXOR(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        TrieNode root = new TrieNode();
        // 将所有的 num 构建到 Trie 数中
        for (int num : nums) {
            TrieNode node = root;
            for (int i = 30; i >= 0; i--) {
                // 看看最高位上是 1 还是 0
                int cur = (num >>> i) & 1;
                if (node.next[cur] == null) {
                    node.next[cur] = new TrieNode();
                }
                node = node.next[cur];
            }
        }
        int res = 0;
        for (int num : nums) {
            TrieNode node = root;
            int xor = 0;
            for (int i = 30; i >= 0; i--) {
                int cur = (num >>> i) & 1;
                if (node.next[cur ^ 1] != null) {
                    xor |= (1 << i);
                    node = node.next[cur ^ 1];
                } else {
                    node = node.next[cur];
                }
            }
            res = Math.max(res, xor);
        }
        return res;
    }
}

参考解答4：使用字典树（Trie）。

public class Solution4 {

    // 参考资料：http://www.cnblogs.com/njufl/p/6403043.html

    private class TrieNode {
        private TrieNode[] next;

        public TrieNode() {
            this.next = new TrieNode[2];
        }
    }

    public int findMaximumXOR(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        TrieNode root = new TrieNode();
        int res = 0;
        for (int num : nums) {
            int xor = 0;
            TrieNode insert = root;
            TrieNode search = root;
            for (int i = 30; i >= 0; i--) {
                int bit = (num >>> i) & 1;
                // 1 变成 0 ，0 变成 1
                int rbit = bit ^ 1;
                if (insert.next[bit] == null) {
                    insert.next[bit] = new TrieNode();
                }
                insert = insert.next[bit];
                if (search != null) {
                    if (search.next[rbit] != null) {
                        xor += (1 << i);
                        search = search.next[rbit];
                    } else {
                        search = search.next[bit];
                    }
                }
            }
            res = Math.max(res, xor);
        }
        return res;
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0421-maximum-xor-of-two-numbers-in-an-array ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。