421. Maximum XOR of Two Numbers in an Array

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ ij < n.

Could you do this in O(n) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.

O(n^2)的方法很简单,主要是O(n)怎么实现
这里可以用trie实现,和字典树一样,这是个binary数,每个node有两个child 0 和 1,存的时候我们位数从后往前(32-0),因为我们要求最大的,不妨从高位bit开始,
这样的话如果高位bit有它对应的亦或存在计算起来方便?

整体结构是先initialize trie,然后遍历nums里的数,对每个数从高位到低,查找是否有与他亦或的位存在,如果存在就到亦或位的child并且更新current sum,没有就到自己的child继续往下。
class Solution {
   class Trie {
        Trie[] children;
        public Trie() {
            children = new Trie[2];
        }
    }
    
    public int findMaximumXOR(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        // Init Trie.
        Trie root = new Trie();
        for(int num: nums) {
            Trie curNode = root;
            for(int i = 31; i >= 0; i --) {
                int curBit = (num >> i) & 1;
                if(curNode.children[curBit] == null) {
                    curNode.children[curBit] = new Trie();
                }
                curNode = curNode.children[curBit];
            }
        }
        int max = Integer.MIN_VALUE;
        for(int num: nums) {
            Trie curNode = root;
            int curSum = 0;
            for(int i = 31; i >= 0; i --) {
                int curBit = (num >> i) & 1;
                if(curNode.children[curBit ^ 1] != null) {
                    curSum += (1 << i);
                    curNode = curNode.children[curBit ^ 1];
                }else {
                    curNode = curNode.children[curBit];
                }
            }
            max = Math.max(curSum, max);
        }
        return max;
    }
}

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/91059/Java-O(n)-solution-using-Trie

 
上一篇:[LeetCode] 53. Maximum Subarray(最大子数组)


下一篇:1026. Maximum Difference Between Node and Ancestor