leetcode421

发表于 更新于 分类于 ，

题目要求

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai< 231.

Find the maximum result of ai XOR aj, where 0 ≤i,j<n.

Could you do this in O(n) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.

现有一个非空的整数数组，问如何能够找出整数数组中两个整数的异或结果的最大值。

思路一：贪婪算法

这里解释一下高分答案贪婪算法的思路。每一次我们都试图假设第i位的异或结果为1，并且判断是否能够从数组中找到任意两个整数，其在该位上的异或值为1。如果找不到，则说明任意两个整数在该位的异或结果只能是0。接着对第i-1位进行同样的判断。从高位开始的原因在于，从贪婪角度的算法看来，我们更希望高位为1，其生成的异或值更大。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
   public int findMaximumXOR(int[] nums) {
       //32位到第i位为止算出的异或最大值
	int maxResult = 0;
	int mask = 0;
	for(int i = 31 ; i>=0 ; i--) {
           //i~32位全为1
		mask |= (1 << i);
		Set<Integer> set = new HashSet<>();
           //取所有整数的前32-i位的结果并保存
		for(int num : nums) {
			set.add(num | mask);
		}
		
           //假设第i位能够异或出结果1
		int greedyTry = maxResult | (1 << i);
           //使用结论a^b=c,则a^c=b。根据该结论，我们假设整数数组中的两个整数在第i为的值为1，且set中存储了所有的a的值，异或出b的值后看b是否也在set中。
		for(int num : set) {
			if(set.contains(greedyTry ^ num)) {
				maxResult = greedyTry;
				break;
			}
		}
	}
	return maxResult;

}

思路二：Trie

假如我们用Trie的数据结构将所有的整数以32位平铺开，一个Trie节点表示第i位是否有为0或是为1的数字：则每个Trie节点有三种可能：

  1. Trie节点无子节点：则表明该节点为叶节点，无需继续处理
  2. Trie节点有一个子节点：表明只有一个数字在该位上的值为0或1
  3. Trie节点有两个子节点：表明该位上有0也有1

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
public int findMaximumXOR2(int[] nums) {
    if (nums.length < 2) {
        return 0;
    }
    //将所有整数存入Trie结构
    TrieNode root = new TrieNode(-1);
    for (int i = 0; i < nums.length; i += 1) {
        addToTrie(root, nums[i]);
    }
    return findMaximum(root, 31);
}

private int findMaximum(TrieNode node, int pos) {
    if (pos == 0) {
        return 0;
    }
    
    //表明在第pos位上只有1，异或结果一定为0
    if (node.zero == null) {
        return findMaximum(node.one, pos - 1);
    }
    //表明在第pos上只有0，异或结果一定为0
    if (node.one == null) {
        return findMaximum(node.zero, pos - 1);
    }
    return findMaximum(node.zero, node.one, pos - 1);
}

private int findMaximum(TrieNode node1, TrieNode node2, int pos) {
    //计算第pos上的异或结果
    int result = (node1.val ^ node2.val) << pos;
    //pos==0代表为叶节点
    if (pos == 0) {
        return result;
    }
    //获取node1的可用子节点和node2的可用子节点
    TrieNode next1 = null;
    TrieNode next2 = null;
    if (node1.zero != null && node1.one == null) {
        next1 = node1.zero;
    } else if (node1.zero == null && node1.one != null) {
        next1 = node1.one;
    }
    if (node2.zero != null && node2.one == null) {
        next2 = node2.zero;
    } else if (node2.zero == null && node2.one != null) {
        next2 = node2.one;
    }
    //满足node1和node2均只有一个子节点，将二者进行迭代比较
    if (next1 != null && next2 != null) {
        return result + findMaximum(next1, next2, pos - 1);
    }
    //node1不为空代表node1只有一个可用子节点，如果子节点为0，则选node2的one子节点，否则选node2的zero子节点
    if (next1 != null) {
        if (next1.val == 0) {
            next2 = node2.one;
        } else {
            next2 = node2.zero;
        }
        return result + findMaximum(next1, next2, pos - 1);
    }
    //同上
    if (next2 != null) {
        if (next2.val == 0) {
            next1 = node1.one;
        } else {
            next1 = node1.zero;
        }
        return result + findMaximum(next1, next2, pos - 1);
    }
    //node1和node2均有两个子节点，则将node1.one和node2.zero 与 node1.zero和node2.one进行比较得出最大异或值
    return result + Math.max(findMaximum(node1.zero, node2.one, pos - 1), findMaximum(node1.one, node2.zero, pos - 1));
}

private void addToTrie(TrieNode root, int x) {
    TrieNode curr = root;
    int[] binary = toBinary(x);
    for (int i = 0; i < binary.length; i += 1) {
        if (binary[i] == 0) {
            if (curr.zero == null) {
                curr.zero = new TrieNode(0);
            }
            curr = curr.zero;
        } else {
            if (curr.one == null) {
                curr.one = new TrieNode(1);
            }
            curr = curr.one;
        }
    }
}

private int[] toBinary(int x) {
    int[] result = new int[31];
    for (int i = 30; i >= 0; i -= 1) {
        result[i] = x & 1;
        x >>= 1;
    }
    return result;
}

static class TrieNode {
    int val;
    TrieNode zero;
    TrieNode one;
    
    public TrieNode(int val) {
        this.val = val;
        zero = null;
        one = null;
    }
}