JAVA solution with trie and bit operation 94% O(n)


  • -1
    T
        /*we use the Trie to solve the problem
        for example [10,20]
        10:0000.... 1010
        20:0000....0001 0010.
        we use every one bit as a Node value;
        then we use two point to analyse whether it should be insert and whether the int[] max should be validate*/
      class TrieNode{
            TrieNode[] next;
            TrieNode(){
                next = new TrieNode[2];
            }
        }
    
        class Trie{
            Set<Integer> set;
            final int bit;
            TrieNode root;
            int[] max;
            Trie(){
                root = new TrieNode();
                max = new int[31];
                bit =(int)Math.pow(2, 30);
                set = new HashSet<>();
            }
            //refresh max[] and insert the number
            public void analyse(int num){
                if (set.contains(num)) {
                    return;
                }
                if (set.isEmpty()) {
                    insertNode(num,root,bit);
                    set.add(num);
                    return;
                }
                set.add(num);
                TrieNode p1 = root;//use the point analyse the insertion
                TrieNode p2 = root;//use the point analyse the refresh
                int index = 0;//the position of the arr[]
                int tmp = bit;// the bit operation initial
                while (index < max.length) {
                    int k =(num & tmp) == 0? 0:1;//get the bit val of ervery position
                    if (p2.next[1 - k] == null) {
                        if (p1.next[k] == null) {
                            p1.next[k] = new TrieNode();
                        }
                        if (max[index] == 1) {
                            insertNode(num,p1.next[k],tmp >> 1);
                            return;
                        }
                        p1 = p1.next[k];
                        p2 = p2.next[k];
                    }else {
                        if (p1.next[k] == null) {
                            p1.next[k] = new TrieNode();
                        }
                       if (max[index] == 0) {
                           max[index] = 1;
                           reFresh(max, index + 1, num, tmp>>1, p1.next[k],p2.next[1 - k]);
                           return;
                       }else {
                           p1 = p1.next[k];
                           p2 = p2.next[1 - k];
                       }
                    }
                    index ++;
                    tmp >>= 1;
                }
    
            }
            //refresh the max[]
            private void reFresh(int[] max, int i, int num, int tmp, TrieNode p1, TrieNode p2) {
                while (i < max.length) {
                    int k =(num & tmp) == 0? 0:1;
                    if (p2.next[1 - k] != null) {
                        max[i] = 1;
                        p2 = p2.next[1 - k];
                    }else {
                        max[i] = 0;
                        p2 = p2.next[k];
                    }
                    if (p1.next[k] == null) {
                        p1.next[k] = new TrieNode();
                    }
                    p1 = p1.next[k];
                    i ++;
                    tmp >>= 1;
                }
            }
            // insert the node
            private void insertNode(int num, TrieNode p1, int tmp) {
                while (tmp != 0) {
                    int k =(num & tmp) == 0? 0:1;
                    if (p1.next[k] == null){
                        p1.next[k] = new TrieNode();
                    }
                    p1 = p1.next[k];
                    tmp >>= 1;
                }
            }
            public int getResult() {
                int res = 0;
                for (int i = 0; i < max.length; i ++) {
                    res += max[i] * Math.pow(2, 30 - i);
                }
                return res;
            }
        }
    
        public int findMaximumXOR(int[] nums) {
            Trie tree = new Trie();
            for (int k : nums) {
                tree.analyse(k);
            }
            return tree.getResult();
        }
    

Log in to reply
 

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