Add Solution.java for 421.Maximum XOR of Two Numbers in an Array

Hinsteny · Hinsteny · commit f1f936175d03 · 2019-06-20T11:18:46.000+08:00
diff --git a/solution/0421.Maximum XOR of Two Numbers in an Array/README.md b/solution/0421.Maximum XOR of Two Numbers in an Array/README.md
@@ -0,0 +1,51 @@
+## 数组中两个数的最大异或值
+### 题目描述
+
+给定一个非空数组，数组中元素为 a0, a1, a2, … , an-1，其中 0 ≤ ai < 231 。
+
+找到 ai 和aj 最大的异或 (XOR) 运算结果，其中0 ≤ i,  j < n 。
+
+示例:
+```
+输入: [3, 10, 5, 25, 2, 8]
+
+输出: 28
+
+解释: 最大的结果是 5 ^ 25 = 28.
+```
+
+### 解法
+异或运算被称为不做进位的二进制加法运算, 且具有一个性质：如果 a ^ b = c 成立，那么a ^ c = b 与 b ^ c = a 均成立。
+再分析一下题目, 要在数组中找到两个数对他们进行异或运算后得到一个最大的异或值, 即这个异或值二进制表示非0最高位要尽可能的靠左同时剩余位尽可能为1;
+整体使用贪心原则, 依次假设整数从左至右第i为1, 然后再使用一个mask与数组中所有数相与得到数据前i位的一个前缀集合, 再把之前一次i-1循环所得到的max加第i位
+为1得到当前i循环中期望的pre-max, 再与前缀集合中的所有数进行异或运算, 如果得到的值也同时在集合中, 表示假设成立, max变为pre-max, 否则直接i+1进行下一个
+循环, 直到i=0算法结束;
+
+```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;
+    }
+}
+```
diff --git a/solution/0421.Maximum XOR of Two Numbers in an Array/Solution.java b/solution/0421.Maximum XOR of Two Numbers in an Array/Solution.java
@@ -0,0 +1,26 @@
+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;
+    }
+}
diff --git a/solution/README.md b/solution/README.md
@@ -765,6 +765,9 @@
 │   └── Solution.py
 ├── 0415.Add Strings
 │   └── Solution.java
+├── 0421.Maximum XOR of Two Numbers in an Array
+│   ├── README.md
+│   └── Solution.java
 ├── 0423.Reconstruct Original Digits from English
 │   └── Solution.cpp
 ├── 0427.Construct Quad Tree
@@ -1056,4 +1059,4 @@
 │   └── Solution.py
 └── 5087.Letter Tile Possibilities
     └── Solution.py
-```
+```
