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 => x^b^b=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;
    }
}
内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/mapoos/p/13681811.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!