题目描述

blablabla

样例

blablabla

算法1

Java 代码

import java.io.*;
import java.util.*;

/**
 * 求给定的一群数里的最大异或对
 */
public class Main {
    class Trie {
        Trie[] child;
        public Trie(){
            child = new Trie[2];
        }
    }

    public int findMaximumXOR(int[] nums) {
        Trie root = new Trie();
        Trie cur;
        for(int num:nums){
            cur = root;
            for(int i = 31; i >= 0;i--){
                int bit = (num >>> i) & 1;
                // if current bit is 0, it will go to children[1]
                // if current bit is 1, it will go to children[0]
                if(cur.child[bit] == null){
                    cur.child[bit] = new Trie(); 
                }
                cur = cur.child[bit];
            }
        }

        int max = Integer.MIN_VALUE;
        for(int num:nums){
            cur = root;
            int curSum = 0;
            for(int i = 31; i>= 0; i--){
                int curBit = (num >>> i) & 1;
                if(cur.child[curBit ^ 1] != null) {
                    curSum += (1 << i);
                    cur = cur.child[curBit ^ 1];
                }else {
                    cur = cur.child[curBit];
                }
            }
            max = Math.max(curSum, max);
        }
        return max;

    }

    void run(){
        int n = jin.nextInt();
        int[] nums = new int[n];
        for (int i = 0 ; i < n ; i++) {
            nums[i] = jin.nextInt();
        }
        System.out.println(findMaximumXOR(nums));
    }

    private Scanner jin = new Scanner(System.in);
    public static void main(String[] args) throws Exception {new Main().run();}
}