Ugly but straight forward Python O(n) Trie solution


  • 2
    Z

    Ugly but straight forward Python Trie solution, first build a Trie with all the nums; then try to "pass" each num in nums through that Trie,
    if the path bifurcates at a node, took the opposite route,and update the current XOR result by adding 1 to the current bit.

    class Solution(object):
        def findMaximumXOR(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            head=[None,None]
            for num in nums:
                node=head
                for bit in range(31,-1,-1):
                    chd=int(bool(num&(1<<bit)))
                    if node[chd]==None:
                        NewNode=[None,None]
                        node[chd]=NewNode
                        node=NewNode
                    else:
                        node=node[chd]
            maxXor=0
            for num in nums:
                node=head
                curXor=0
                for bit in range(31,-1,-1):
                    chd=int(bool(num&(1<<bit)))
                    if node[1^chd]:
                        curXor|=1<<bit
                        node=node[1^chd]
                    else:
                        node=node[chd] 
                maxXor=max(maxXor,curXor)
                
            return maxXor
    

  • 0
    S

    It is O(n*log(n)), not O(n).


  • 0

    @stould No, it's O(NlogV) = O(32 * N) = O(N)


  • 0
    A

    @zhang.liangkai.5 said in Ugly but straight forward Python O(n) Trie solution:

    can you explain or add comment to your code please


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.