421.-maximum-xor-of-two-numbers-in-an-array.md

421. Maximum XOR of Two Numbers in an Array

{% tabs %} {% tab title="Python-TLE" %}

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
    
    ## 首先这个的是没问题的，
    ## 就是复杂度超了，
    ## 感觉就是动态规划 
    
        if not nums: return 0
        ans = -float("inf")
        for i in range(len(nums)):
            for  j in range(i,len(nums)):
                ans = max(ans,nums[i]^nums[j])
                
        return ans

{% endtab %}

{% tab title="贪心+set" %}

# 如果 a ^ b = c 成立，那么a ^ c = b 与 b ^ c = a 均成立。 真理

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        ans = 0
        mask = 0

        for i in range(31, - 1, -1 ):
            ## 从最左边开始看，看数位到底是多少
            s = set()
            ## 这个的目的就是不断更新“100000” ，一开始是31 个 最后全都是11111
            mask = mask | (1 << i )

            for num in nums: ## 记录最高位为1 的潜在客户 
                ## 与都是找都是1 的
                s.add(num & mask)

            # 假设最大值存在与数组当中， 这样才能利用抑或运算的知识点
            tmp = ans | (1 << i)
            for ele in s:
                if tmp ^ ele in s:
                    ans= tmp
                    break

        return ans

{% endtab %} {% endtabs %}