面试算法67:最大的异或

2023-12-21 16:31:56

题目

输入一个整数数组(每个数字都大于或等于0),请计算其中任意两个数字的异或的最大值。例如,在数组[1,3,4,7]中,3和4的异或结果最大,异或结果为7。

分析

整数的异或有一个特点,如果两个相同数位异或的结果是0,那么两个相反的数位异或的结果为1。如果想找到某个整数k和其他整数的最大异或值,那么尽量找和k的数位不同的整数。
因此,这个问题可以转化为查找的问题,而且还是按照整数的二进制数位进行查找的问题。需要将整数的每个数位都保存下来。前缀树可以实现这种思路,前缀树的每个节点对应整数的一个数位,路径对应一个整数。

public class Test {
    public static void main(String[] args) {
        int[] dict = {1, 3, 4, 7};
        System.out.println(findMaximumXOR(dict));
    }

    static class TrieNode {
        public TrieNode[] children;

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

    private static TrieNode buildTrie(int[] nums) {
        TrieNode root = new TrieNode();
        for (int num : nums) {
            TrieNode node = root;
            for (int i = 31; i >= 0; i--) {// 先保存高位
                int bit = (num >> i) & 1;
                if (node.children[bit] == null) {
                    node.children[bit] = new TrieNode();
                }

                node = node.children[bit];
            }
        }

        return root;
    }

    public static int findMaximumXOR(int[] nums) {
        TrieNode root = buildTrie(nums);
        int max = 0;
        for (int num : nums) {
            TrieNode node = root;
            int xor = 0;
            for (int i = 31; i >= 0; i--) {// 从高位开始比较
                int bit = (num >> i) & 1;
                if (node.children[1 - bit] != null) {// 存在和bit不一样的bit
                    xor = (xor << 1) + 1;
                    node = node.children[1 - bit];
                }
                else {
                    xor = xor << 1;
                    node = node.children[bit];
                }
            }

            max = Math.max(max, xor);
        }
        return max;
    }
}

文章来源:https://blog.csdn.net/GoGleTech/article/details/135132770
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。