421. Maximum XOR of Two Numbers in an Array

题目描述和难度

  • 题目描述:

给定一个非空数组,数组中元素为 a0, a1, a2, … , an-1,其中 0 ≤ ai < 231 

找到 ai 和a最大的异或 (XOR) 运算结果,其中0 ≤ i,  j <

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

示例:

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

输出: 28

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

思路分析

求解关键:

参考解答

参考解答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