Java 40ms Solution with Trie


  • 0
    L
    public class Solution{
    	private TrieNode root = new TrieNode(0);
    	private int max = 0;
    	
    	class TrieNode {
    		int value;
    		TrieNode[] childs;
    		public TrieNode(int value) {
    			this.value = value;
    			this.childs = new TrieNode[2];
    		}
    	}
    	
    	private void insert(int num){
    		TrieNode cur = root;
    		for(int i=30;i>=0;i--){
    			int bit = (num >> i) & 1;
    			if(cur.childs[bit]==null){
    				cur.childs[bit] = new TrieNode(bit);
    			}
    			cur = cur.childs[bit];
    		}
    	}
    	
    	private void createTrie(int[] nums){
    		for(int num : nums){
    			insert(num);
    		}
    	}
    	
    	private void findMax(TrieNode node1,TrieNode node2,int v){
    		if(node1==null && node2==null){
    			max = Math.max(max, v);
    			return;
    		}
    		v = v << 1;
    		if(node1==null){
    			findMax(node2.childs[0], node2.childs[1],v);
    		}else if(node2==null){
    			findMax(node1.childs[0], node1.childs[1],v);
    		}else{
    			if(node1.value!=node2.value){
    				v |= 1;
    			}
    			boolean flag = true;
    			if(node1.childs[0]!=null && node2.childs[1]!=null){
    				flag = false;
    				findMax(node1.childs[0], node2.childs[1],v);
    			}
    			if(node1.childs[1]!=null && node2.childs[0]!=null){
    				flag = false;
    				findMax(node1.childs[1], node2.childs[0],v);
    			}
    			if(flag){
    				if(node1.childs[0]!=null){
    					findMax(node1.childs[0], node2.childs[0],v);
    				}else if(node1.childs[1]!=null){
    					findMax(node1.childs[1], node2.childs[1],v);
    				}else{
    					max = Math.max(max, v);
    				}
    			}
    		}
    	}
    	
        public int findMaximumXOR(int[] nums) {
        	createTrie(nums);
        	findMax(root.childs[0], root.childs[1],0);
            return max;
        }
    }
    

Log in to reply
 

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