Maximum XOR of Two Numbers in an Array

leap_frog 發(fā)布于2019-08-14 17:18 / 2224人閱讀

摘要：把所有放進(jìn)，之后對每一個從最高位找是否存在和當(dāng)前不同的。把多帶帶寫一個函數(shù)，結(jié)果了，所以放一起了。。如果有就把放進(jìn)去，當(dāng)前結(jié)果累計到下一個循環(huán)。把所有放進(jìn)里面找出中是否有兩個數(shù)后等于的結(jié)果有就更新第二步根據(jù)

標(biāo)題文字

鏈接：https://leetcode.com/problems...

可以用trie tree來做。把所有num放進(jìn)tree，之后對每一個num從最高位找是否存在和當(dāng)前bit不同的path。把build tree多帶帶寫一個函數(shù)，結(jié)果TLE了，所以放一起了。。

public class Solution {
    public int findMaximumXOR(int[] nums) {
        /* trie tree: root is the largest bit
         * 32 bits
         */
        TrieNode root = new TrieNode();
        for(int num : nums) {
            TrieNode node = root;
            for(int i = 31; i >= 0; i--) {
                int bit = (num >> i) & 1;
                if(node.children[bit] == null) node.children[bit] = new TrieNode();
                node = node.children[bit];
            }
        }
        
        int globalMax = Integer.MIN_VALUE;
        
        for(int num : nums) {
            int local = 0;
            TrieNode node = root;
            for(int i = 31; i >= 0; i--) {
                int bit = (num >> i) & 1;
                if(node.children[bit ^ 1] != null) {
                    local += (1 << i);
                    node = node.children[bit ^ 1];
                }
                else node = node.children[bit];
            }
            globalMax = Math.max(globalMax, local);
        }
        return globalMax;
    }
    
    class TrieNode {
        TrieNode[] children = new TrieNode[2];
    }
    
}

看到discussion還有一種簡單的方法，從最高位開始掃，每次在nums里面找有沒有兩個數(shù)XOR可以等于1。如果有就把1放進(jìn)去，當(dāng)前結(jié)果累計到下一個循環(huán)。用一個set存到第i位位置的數(shù)，然后通過XOR就能找到有沒有可以匹配的數(shù)。

把所有num(31, i)放進(jìn)set里面

找出set中是否有兩個數(shù)XOR后等于i = 1的結(jié)果

有就更新globalMax

第二步根據(jù) x ^ y = z, then x ^ z = y

public class Solution {
    public int findMaximumXOR(int[] nums) {
         int globalMax = 0, highestBits = 0;
         for(int i = 31; i >= 0; i--) {
             // 1000 -> 1100 -> 1110 -> 1111
             highestBits = highestBits | (1 << i);
             Set set = new HashSet();
             for(int num : nums) {
                 set.add(num & highestBits);
             }
             
             // find if current bit can be 1
             int addOne = globalMax | (1 << i);
             for(int num : set) {
                 if(set.contains(num ^ addOne)) {
                     globalMax = addOne;
                     break;
                 }
             }
         }
         return globalMax;
    }

}