“This is the 19th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

describe

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.
Copy the code

Note:

1 <= nums.length <= 2 * 10^5
0 <= nums[i] <= 2^31 - 1
Copy the code

parsing

In the range 0 <= I <= j < n, nums[I] XOR nums[j] is maximal. Because the maximum length of nums is 2 * 10^5, and each number is quite large, it will be a lot of computation. If we use the traditional violent solution, the two-layer loop to find the maximum, the time complexity is O(n^2), It’s bound to run out of time. So the challenge is to find an algorithm that compresses O(n^2) down to O(n).

If we have a numS number 010101, we want to find a number with xor operation to maximize its ideal state. 101010 does not necessarily appear in NUMS, so we can use a similar idea:

  • From the remaining nums elements, find the set of digits with the first bit of binary 1
  • If there are more than one element in the set, look for the set of numbers whose second digit is 0
  • Of course, if none of the optional elements fits in any one of the bits, then all of them remain in the set, because there is no better choice, and continue to look for the next bit
  • We repeat the process until we find only one element in the set, which is the number with the greatest xor to 010101 in NUMs

In fact, we should know that the fastest way to see if the first n digits are valid is to use the Trie tree structure, because we can easily find the largest xOR result by storing all the digits in a single N-bit binary tree. The time complexity is O(32) at most, because we do not need to traverse NUMS, just need to find the first N (n<=32) layer Trie tree nodes. Another is that the Trie saves a lot of space.

answer

class TrieNode:
    def __init__(self):
        self.children = {}                      
        self.val = 0                                  
class Trie:
    def __init__(self, n):
        self.root = TrieNode()                        
        self.n = n                                    
        
    def add_num(self, num):
        node = self.root 
        for tmp in range(self.n, -1, -1):           
            val = 1 if num & (1 << tmp) else 0     
            if val not in node.children:
                node.children[val] = TrieNode()
            node = node.children[val]
        node.val = num
class Solution(object):
    def findMaximumXOR(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        L = len(bin(max(nums))) - 2             
        trie = Trie(L)
        for num in nums: 
            trie.add_num(num)            
        result = 0
        for num in nums:                              
            node = trie.root 
            for tmp in range(L, -1, -1):
                val = 1 if num & (1 << tmp) else 0  
                node = node.children[1-val] if 1-val in node.children else node.children[val] 
            result = max(result, num ^ node.val)          
        return result              	      	
Copy the code

The results

Runtime: Each node in the linked list is linked to an Array in the linked list. Submissions in Python online submissions for Maximum XOR of Two Numbers in an Array.Copy the code

The original link

Leetcode.com/problems/ma…

Your support is my biggest motivation