README.md

421. 数组中两个数的最大异或值

English Version

题目描述

给定一个非空数组，数组中元素为 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.

解法

哈希表或前缀树实现。

Python3

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        max = 0
        mask = 0
        for i in range(30, -1, -1):
            current = 1 << i
            # 期望的二进制前缀
            mask = mask ^ current
            # 在当前前缀下, 数组内的前缀位数所有情况集合
            s = set()
            for num in nums:
                s.add(num & mask)
            # 期望最终异或值的从右数第i位为1, 再根据异或运算的特性推算假设是否成立
            flag = max | current
            for prefix in s:
                if prefix ^ flag in s:
                    max = flag
                    break
        return max

class Trie:
    def __init__(self):
        self.left = None
        self.right = None

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        self.root = Trie()
        self.highest = 30

        def add(num):
            node = self.root
            for i in range(self.highest, -1, -1):
                bit = (num >> i) & 1
                if bit == 0:
                    if node.left is None:
                        node.left = Trie()
                    node = node.left
                else:
                    if node.right is None:
                        node.right = Trie()
                    node = node.right

        def cal(num):
            node = self.root
            res = 0
            for i in range(self.highest, -1, -1):
                bit = (num >> i) & 1
                if bit == 0:
                    if node.right:
                        res = res * 2 + 1
                        node = node.right
                    else:
                        res = res * 2
                        node = node.left
                else:
                    if node.left:
                        res = res * 2 + 1
                        node = node.left
                    else:
                        res = res * 2
                        node = node.right
            return res

        res = 0
        for i in range(1, len(nums)):
            add(nums[i - 1])
            res = max(res, cal(nums[i]))
        return res

Java

class Solution {

    public int findMaximumXOR(int[] numbers) {
        int max = 0;
        int mask = 0;
        for (int i = 30; i >= 0; i--) {
            int current = 1 << i;
            // 期望的二进制前缀
            mask = mask ^ current;
            // 在当前前缀下, 数组内的前缀位数所有情况集合
            Set<Integer> set = new HashSet<>();
            for (int j = 0, k = numbers.length; j < k; j++) {
                set.add(mask & numbers[j]);
            }
            // 期望最终异或值的从右数第i位为1, 再根据异或运算的特性推算假设是否成立
            int flag = max | current;
            for (Integer prefix : set) {
                if (set.contains(prefix ^ flag)) {
                    max = flag;
                    break;
                }
            }
        }
        return max;
    }
}

前缀树。

class Solution {
    private static final int HIGHEST = 30;
    private Trie root;

    public int findMaximumXOR(int[] nums) {
        int res = 0;
        root = new Trie();
        for (int i = 1; i < nums.length; ++i) {
            add(nums[i - 1]);
            res = Math.max(res, cal(nums[i]));
        }
        return res;
    }

    private int cal(int num) {
        Trie node = root;
        int res = 0;
        for (int i = HIGHEST; i >= 0; --i) {
            int bit = (num >> i) & 1;
            if (bit == 0) {
                if (node.right != null) {
                    res = res * 2 + 1;
                    node = node.right;
                } else {
                    res = res * 2;
                    node = node.left;
                }
            } else {
                if (node.left != null) {
                    res = res * 2 + 1;
                    node = node.left;
                } else {
                    res = res * 2;
                    node = node.right;
                }
            }
        }
        return res;
    }

    private void add(int num) {
        Trie node = root;
        for (int i = HIGHEST; i >= 0; --i) {
            int bit = (num >> i) & 1;
            if (bit == 0) {
                if (node.left == null) {
                    node.left = new Trie();
                }
                node = node.left;
            } else {
                if (node.right == null) {
                    node.right = new Trie();
                }
                node = node.right;
            }
        }
    }
}

class Trie {
    public Trie left;
    public Trie right;
}

C++

class Trie {
public:
    Trie* left;
    Trie* right;
};

class Solution {
public:
    int highest = 30;
    Trie* root;

    int findMaximumXOR(vector<int>& nums) {
        root = new Trie();
        int res = 0;
        for (int i = 1; i < nums.size(); ++i)
        {
            add(nums[i - 1]);
            res = max(res, cal(nums[i]));
        }
        return res;
    }

    int cal(int num) {
        Trie* node = root;
        int res = 0;
        for (int i = highest; i >= 0; --i)
        {
            int bit = (num >> i) & 1;
            if (bit == 0)
            {
                if (node->right)
                {
                    res = res * 2 + 1;
                    node = node->right;
                }
                else
                {
                    res = res * 2;
                    node = node->left;
                }
            }
            else
            {
                if (node->left)
                {
                    res = res * 2 + 1;
                    node = node->left;
                }
                else
                {
                    res = res * 2;
                    node = node->right;
                }
            }
        }
        return res;
    }

    void add(int num) {
        Trie* node = root;
        for (int i = highest; i >= 0; --i)
        {
            int bit = (num >> i) & 1;
            if (bit == 0)
            {
                if (!node->left) node->left = new Trie();
                node = node->left;
            }
            else
            {
                if (!node->right) node->right = new Trie();
                node = node->right;
            }
        }
    }
};

Go

const highest = 30

type trie struct {
	left, right *trie
}

func (root *trie) add(num int) {
	node := root
	for i := highest; i >= 0; i-- {
		bit := (num >> i) & 1
		if bit == 0 {
			if node.left == nil {
				node.left = &trie{}
			}
			node = node.left
		} else {
			if node.right == nil {
				node.right = &trie{}
			}
			node = node.right
		}
	}
}

func (root *trie) cal(num int) int {
	node := root
	res := 0
	for i := highest; i >= 0; i-- {
		bit := (num >> i) & 1
		if bit == 0 {
			if node.right != nil {
				res = res*2 + 1
				node = node.right
			} else {
				res = res * 2
				node = node.left
			}
		} else {
			if node.left != nil {
				res = res*2 + 1
				node = node.left
			} else {
				res = res * 2
				node = node.right
			}
		}
	}
	return res
}

func findMaximumXOR(nums []int) int {
	root := &trie{}
	res := 0
	for i := 1; i < len(nums); i++ {
		root.add(nums[i-1])
		res = max(res, root.cal(nums[i]))
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

...