leetcode_421

发表于   |   分类于

Maximum XOR of Two Numbers in an Array

题目戳这

题意

给定一个数组，求数组中x^y的最大值，x，y是属于这个数组的任意两个数。

解法

题解在这，这道题目挺神奇的。。

不太好理解。。用的是a^b=c,则b^c=a这个亦或的特性。。多看几遍能懂。。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def findMaximumXOR(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        mask = 0
        mmax = 0
        for i in range(31,-1,-1):
            mask |= (1<<i)	# mask每个循环都在积累
            s = set()
            for x in nums:
                s.add(x&mask)
            
            tmp = mmax | (1<<i)	# 假设tmp为最大值
            for x in s:
                if tmp ^ x in s: # x中已经包含了b，只要求a是否在集合s中
                    mmax = tmp	# 存在的话就可以跳出
                    break
            
        return mmax