LeetCode 算法 每日一题 421.数组中两个数的最大异或值
421.数组中两个数的最大异或值
题目描述
给你一个整数数组nums，返回nums[i] XOR nums[j]的最大运算结果，其中0 ≤ i ≤ j < n。
进阶：你可以在O(n)的时间解决这个问题吗？
示例1
输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.
示例2
输入：nums = [0]
输出：0
示例3
输入：nums = [2,4]
输出：6
示例4
输入：nums = [8,10,2]
输出：10
示例5
输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127
提示
1 <= nums.length <= 2 * 104
0 <= nums[i] <= 231 - 1
O(n)时间复杂度以内
把每个数字按bit位拆分成0-1字典树。
将每个数字的二进制位，从高位到低位存储到前缀树中，也就是说前缀树中仅有0和1这两个数字。
每个数字跟字字典树进行异或，其中最长的分支，就是最大值。
代码演示
Java 0-1字典树
public class OneQuestionPerDay421 {
public static void main(String[] args) {
Solution s = new Solution();
int array1[] = {3,10,5,25,2,8};
System.out.println(s.findMaximumXOR(array1));
int array2[] = {0};
System.out.println(s.findMaximumXOR(array2));
int array3[] = {2,4};
System.out.println(s.findMaximumXOR(array3));
int array4[] = {8,10,2};
System.out.println(s.findMaximumXOR(array4));
int array5[] = {14,70,53,83,49,91,36,80,92,51,66,70};
System.out.println(s.findMaximumXOR(array5));
}
}
class Trie {
Trie left = null;
Trie right = null;
}
class Trie {
Trie left = null;
Trie right = null;
}
class Solution {
Trie root = new Trie();
public int findMaximumXOR(int[] nums) {
int n = nums.length;
int x = 0;
for (int i = 1; i < n; ++i) {
append(nums[i - 1]);
x = Math.max(x, check(nums[i]));
}
return x;
}
public void append(int num) {
Trie cur = root;
for (int k = 1 << 30; k > 0; k >>= 1) {
int bit = num & k;
if (bit == 0) {
if (cur.left == null) {
cur.left = new Trie();
}
cur = cur.left;
}
else {
if (cur.right == null) {
cur.right = new Trie();
}
cur = cur.right;
}
}
}
public int check(int num) {
Trie cur = root;
int x = 0;
for (int k = 1 << 30; k > 0; k >>= 1) {
int bit = num & k;
if (bit == 0) {
if (cur.right != null) {
cur = cur.right;
x += k;
} else {
cur = cur.left;
}
} else {
if (cur.left != null) {
cur = cur.left;
x += k;
} else {
cur = cur.right;
}
}
}
return x;
}
}
Java 提交结果
执行用时：25 ms, 在所有 Java 提交中击败了95.96% 的用户
内存消耗：42.5 MB, 在所有 Java 提交中击败了61.80% 的用户
非O(n)以内时间复杂度代码演示
Java/C++ 暴力枚举
public class OneQuestionPerDay421 {
public static void main(String[] args) {
Solution s = new Solution();
int array1[] = {3,10,5,25,2,8};
System.out.println(s.findMaximumXOR(array1));
int array2[] = {0};
System.out.println(s.findMaximumXOR(array2));
int array3[] = {2,4};
System.out.println(s.findMaximumXOR(array3));
int array4[] = {8,10,2};
System.out.println(s.findMaximumXOR(array4));
int array5[] = {14,70,53,83,49,91,36,80,92,51,66,70};
System.out.println(s.findMaximumXOR(array5));
}
}
class Solution {
public int findMaximumXOR(int[] nums) {
int result = 0;
for(int i = 0; i < nums.length; i++)
for(int j = i; j < nums.length; j++)
result = Math.max(nums[i] ^ nums[j], result);
return result;
}
}
#include <bits/stdc++.h>
using namespace std;
const int MIN_INT = 0x80000000;
class Solution {
public:
int Max(int a,int b){
return a > b ? a : b;
}
int findMaximumXOR(vector<int>& nums) {
int i,j,result = MIN_INT;
int n = nums.size();
for(i = 0;i < n;i++)
for(j = i;j < n;j++)
result = Max(nums[i] ^ nums[j],result);
return result;
}
};
int main()
{
Solution s;
int array1[6] = {3,10,5,25,2,8};
int array2[1] = {0};
int array3[2] = {2,4};
int array4[3] = {8,10,2};
int array5[12] = {14,70,53,83,49,91,36,80,92,51,66,70};
vector<int> nums1(array1,array1 + 6);
cout << s.findMaximumXOR(nums1) << endl;
vector<int> nums2(array2,array2 + 1);
cout << s.findMaximumXOR(nums2) << endl;
vector<int> nums3(array3,array3 + 2);
cout << s.findMaximumXOR(nums3) << endl;
vector<int> nums4(array4,array4 + 3);
cout << s.findMaximumXOR(nums4) << endl;
vector<int> nums5(array5,array5 + 12);
cout << s.findMaximumXOR(nums5) << endl;
return 0;
}
Java 提交结果
执行用时：463 ms, 在所有 Java 提交中击败了6.68% 的用户
内存消耗：38.8 MB, 在所有 Java 提交中击败了98.60% 的用户
C++ 提交结果 超出时间限制