题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

O(n)

时间复杂度

参考文献

yxc yyds!!!

JAVA 代码

//万能开头：
import java.util.Scanner;
import java.lang.Math;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.lang.Comparable;
import java.util.Collections;
import java.util.Map;
import java.util.HashMap;
import java.util.NavigableMap;
import java.util.TreeMap;
import java.util.PriorityQueue;
import java.util.Queue;
class Main{
static class Trie{
int val = 2;
Trie left; // 0
Trie right; // 1
public Trie(int v){
val = v;
}
}

//建立Trie
static void insert(int srcVal){
    Trie node = root;
    for(int i=30; i>=0; i--){
        int xorVal = (srcVal >> i) & 1;
        if(xorVal == 0){
            if(node.left == null){
                node.left = new Trie(0);
            }
            node = node.left;
        }else if(xorVal == 1){
            if(node.right == null){
                node.right = new Trie(1);
            }
            node = node.right;
        }
    }
}
/**
 * 尽量找每一位的相反位 ,找不到就是使用相同位
 **/
static int queryXor(int val){
    int ans = 0;
    Trie node = root;
    for(int i=30; i>=0; i--){
        int xorVal = (val >> i) & 1;
        if(xorVal == 1){ //走左节点
            if(node.left != null){
                node = node.left;
            }else if(node.right != null){
                ans += 1<<i;
                node = node.right;
            }else break;   
        }else if(xorVal == 0){//走右分支
            if(node.right != null){
                ans += 1<<i;
                node = node.right;
            }else if(node.left != null){
                node = node.left;
            }else{
                break;
            }
        }
    }
    return ans; 
}
static Scanner sc = new Scanner(System.in);
static Trie root = new Trie(2);
public static void main(String []args){
    int N = sc.nextInt();
    int []arr = new int [N];
    for(int i=0;i<N;i++){
        insert((arr[i] =sc.nextInt())); 
    }
    int res = 0;
    for(int i=0; i<N; i++){
        res = Math.max(res, queryXor(arr[i]) ^ arr[i]); 
    }
    System.out.println(res);
}

}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla