[LeetCode] Maximum XOR of Two Numbers in an Array 数组中异或值最大的两个数字

简介:

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 ≤ ij < 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.

这道题是一道典型的位操作Bit Manipulation的题目,我开始以为异或值最大的两个数一定包括数组的最大值,但是OJ给了另一个例子{10,23,20,18,28},这个数组的异或最大值是10和20异或,得到30。那么只能另辟蹊径,正确的做法是按位遍历,题目中给定了数字的返回不会超过231,那么最多只能有32位,我们用一个从左往右的mask,用来提取数字的前缀,然后将其都存入set中,我们用一个变量t,用来验证当前位为1再或上之前结果res,看结果和set中的前缀异或之后在不在set中,这里用到了一个性质,若a^b=c,那么a=b^c,因为t是我们要验证的当前最大值,所以我们遍历set中的数时,和t异或后的结果仍在set中,说明两个前缀可以异或出t的值,所以我们更新res为t,继续遍历,如果上述讲解不容易理解,那么建议自己带个例子一步一步试试,并把每次循环中set中所有的数字都打印出来,基本应该就能理解了,参见代码如下:

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int res = 0, mask = 0;
        for (int i = 31; i >= 0; --i) {
            mask |= (1 << i);
            set<int> s;
            for (int num : nums) {
                s.insert(num & mask);
            }
            int t = res | (1 << i);
            for (int prefix : s) {
                if (s.count(t ^ prefix)) {
                    res = t;
                    break;
                }
            }
        }
        return res;
    }
};

本文转自博客园Grandyang的博客,原文链接:数组中异或值最大的两个数字[LeetCode] Maximum XOR of Two Numbers in an Array ,如需转载请自行联系原博主。

目录
打赏
0
0
0
0
5351
分享
相关文章
CF617E XOR and Favorite Number(异或前缀和+莫队)
CF617E XOR and Favorite Number(异或前缀和+莫队)
77 0
有一个整数数组,长度为9,数组里的值是多少不清楚,但是知道数组中有8个值是相等,其中一个小于其他8个值,目前有一个标准函数,compare(int[] a, int[] b),返回0相等1大于
有一个整数数组,长度为9,数组里的值是多少不清楚,但是知道数组中有8个值是相等,其中一个小于其他8个值,目前有一个标准函数,compare(int[] a, int[] b),返回0相等1大于
137 5
|
10月前
【Leetcode】两数之和,给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
【Leetcode】两数之和,给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
|
10月前
|
C语言中通过INT_MAX判断两个非负整数相加是否溢出
C语言中通过INT_MAX判断两个非负整数相加是否溢出
205 0
LeetCode:1_Two_Sum | 两个元素相加等于目标元素 | Medium
题目: Given an array of integers, find two numbers such that they add up to a specific target number.
856 0
LeetCode 191 Number of 1 Bits(1 比特的数字们)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50506429 翻译 写一个函数获取一个无符号整型数,并且返回它的“1”比特的数目(也被叫做Hamming weight)。
1017 0
二分思想判断数组中是否有两数和为sum
1 /* 2 一个N个整数的无序数组,给你一个数sum,求出数组中是否存在两个数,使他们的和为sum O(nlogn) 3 解题思路:先排序 在左右夹击判断,类似二分查找的思想。 4 */ 5 #include 6 #include 7 int find(int ...
761 0