leetcode 421. Maximum XOR of Two Numbers in an Array 最大的异或运算值 + 位运算

向右看齐 2022-06-04 10:11 197阅读 0赞

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.

题意很简单，直接循环来做肯定超时，后来想了很久不知道怎么做，我觉得直接计算挺不错的

目中给定了数字的返回不会超过231,那么最多只能有32位，我们用一个从左往右的mask，用来提取数字的前缀，然后将其都存入set中，我们用一个变量t，用来验证当前位为1再或上之前结果res，看结果和set中的前缀异或之后在不在set中，这里用到了一个性质，若a^b=c，那么a=b^c，因为t是我们要验证的当前最大值，所以我们遍历set中的数时，和t异或后的结果仍在set中，说明两个前缀可以异或出t的值，所以我们更新res为t，继续遍历，如果上述讲解不容易理解，那么建议自己带个例子一步一步试试，并把每次循环中set中所有的数字都打印出来，基本应该就能理解了，参见代码如下：

参考这个链接[\[LeetCode\] Maximum XOR of Two Numbers in an Array 数组中异或值最大的两个数字][LeetCode_ Maximum XOR of Two Numbers in an Array]

这个方法肯定想不到

代码如下:

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    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;
        }
    
        int findMaximumXORByLoop(vector<int>& nums)
        {
            if (nums.size() <= 1)
                return 0;
            int res = numeric_limits<int>::min();
            for (int i = 0; i < nums.size(); i++)
            {
                for (int j = i + 1; j < nums.size(); j++)
                {
                    res = max(res, nums[i] ^ nums[j]);
                }
            }
            return res;
        }
    };

[LeetCode_ Maximum XOR of Two Numbers in an Array]: https://www.cnblogs.com/grandyang/p/5991530.html