0421. Maximum XOR of Two Numbers in an Array (M)

题目

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.

题意

在数组中选取两个数进行异或，求能够得到的最大值。

思路

解题需要用到异或的性质：x^b=a => xb=a^b => a^b=x。为了得到最大值，应使最终结果ans的高位尽可能为1。从第32位向第1位遍历，每次取出所有数到当前位的前缀，存入到HashSet中；x由上一次遍历得到的ans将当前位设为1得到，将x与任意一个前缀b异或，如果得到的结果a也在HashSet中，说明存在两个前缀异或能够得到x，因此ans当前位确实为1，用x更新ans，否则ans保持不变(即当前位保持为1)。可以看到每次遍历的作用是确定了最终数在相应位是0还是1。

代码实现

Java

class Solution {
    public int findMaximumXOR(int[] nums) {
        int ans = 0;
        int mask = 0;
        for (int i = 31; i >= 0; i--) {
            Set<Integer> set = new HashSet<>();
            mask |= 1 << i;
            for (int num : nums) {
                int prefix = mask & num;
                int tmp = (1 << i) | ans;
                if (set.contains(tmp ^ prefix)) {
                    ans = tmp;
                    break;
                }
                set.add(prefix);
            }
        }
        return ans;
    }
}