最大异或

给定一个正整数数组，找出两个元素，使得它们的异或：a ^ b 最大。

让我们举个例子来了解需要实现什么。

如果数组元素是：12, 15, 9。

我们需要找出从给定数组中任取两个整数可能产生的最大异或值。

可能的异或值有

12^15=3.

12^9=5.

15^9=6.

在上面的结果中，最大异或值为 6，所以答案是 6。

让我们再举一个例子来详细理解。

如果数组元素是 13 11 35 3 32。

如果我们对所有可能的组合应用异或，我们会得到一个最大异或值 46。

现在，我们需要为此实现代码，即找出数组中任意两个值进行异或的最大值。

代码

输出

说明

输入读取

程序从标准输入读取一个整数 t。这表示测试用例的数量。

测试用例循环

程序然后进入一个循环，该循环迭代 t 次，代表每个测试用例。

数组初始化

在循环内，从标准输入读取一个长整型 n，表示数组的大小。

数组填充

声明一个名为 vec 的向量来存储 n 个整数。

然后程序进入另一个循环以读取 n 个整数并填充向量。

按位异或运算

程序初始化一个整数变量并将它设置为 0。

然后它使用嵌套循环遍历向量 (vec) 中的所有元素对，对每一对执行按位异或运算 (^)。

寻找最大异或值

将异或运算的结果与 ans 的当前值进行比较，并将最大值存储在 ans 中。

这个过程将一直持续到向量中的所有元素对都被考虑完毕。

输出

最后，打印当前测试用例的最大异或值 (ans) 到标准输出。

让我们讨论时间和空间复杂度

时间复杂度

输入读取

读取整数 t 需要常数时间。

测试用例循环

测试用例循环运行 t 次，其中 t 是测试用例的数量。

数组填充

数组/向量用 n 个元素填充，其中 n 是每个测试用例的数组大小。

按位异或运算

嵌套循环遍历数组/向量中的所有元素对。

这导致每个测试用例的时间复杂度为 O(n^2)，其中 n 是数组大小。

输出

打印结果需要常数时间。

嵌套循环主导了整体时间复杂度，导致 O(t * n^2)，其中 t 是测试用例的数量，n 是每个测试用例的数组大小。

空间复杂度

输入变量

输入变量，包括整数 t 和长整型 n，决定了空间复杂度。

这些变量占用常数空间。

向量 vec

向量 vec 用于存储数组元素。

其空间复杂度为 O(n)，其中 n 是每个测试用例的数组大小。

其他变量

其他变量，如 ans，是标量，占用常数空间。

整体空间复杂度为 O(n)，其中 n 是任何测试用例的最大数组大小。

总结

时间复杂度： O(t * n^2)

空间复杂度：O(n)