Give you an array of integers, nums, and return the maximum result of nums[i] XOR nums[j]. Where 0<=i<=j<n
Tips:
1 <= nums.length <= 2 * 104
0 <= nums[i] <= 231 - 1
Example 1:
Input: nums = [3,10,5,25,2,8]
Output: 28
Interpretation: The maximum result of the operation is 5 XOR 25 = 28.
Example 2:
Input: nums = [0]
Output: 0
Analysis: The initial thought was violent search, with a time complexity of 0(N^2), which unfortunately timed out. The code is as follows:
class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
//Try Violence Law First
int n=nums.size();
int maxone=0;
for(int i=0; i<n-1;i++){
for(int j=i+1; j<n;j++){
maxone=max(nums[i]^nums[j],maxone);
}
}
return maxone;
}
};
．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．
Since the time complexity of 0(N^2) will time out, a new way of thinking is needed to reduce the time complexity. In this topic, the characteristic of XOR should be brought into play. Below is a passable solution to this problem. Its basic idea is to apply the principle of greed!
The key to this question is that the ultimate maximum XOR result must be the number (i.e., the largest number) of all numbers with the highest position being the first 1. The main idea of the algorithm is to assume that the maximum XOR value we require is X. According to the definition of the topic, x is a binary number of up to 31 bits. We assume that the highest bit of X is 1 every time. Then we continuously update the number of bits of X to make further assumptions. If we can update 1 for 1, we cannot assign 0 for 1 until all the 31 bits of X are assigned. Then the largest x comes out.
You can see that the first assignment is acceptable for a number XOR operation in the original array, and then the second assignment is based on the first result to determine if Assignment 1 is acceptable, although we don't know which two numbers XOR will ultimately achieve the maximum result. However, it can be guaranteed that the judgment of each step can actually exist by some two numerical operations, because the operation of each step is based on the result bits of the previous step, there will be no judgment of 1 or 0 for a certain bit regardless of the previous digits. This may result in the ultimate maximum XOR result coming from a valid XOR with different digits and different bits, rather than from an XOR with two specific digits.
With all this said, the key is how to determine if the n-th sign of x after going is 1. To describe it in language is:
x
=
a
i
⊕
a
j
x=a_i⊕a_j
x=ai aj, then
x
k
=
a
i
k
⊕
a
j
k
x^k=a^k_i⊕a^k_j
xk=aik ajk, then
a
j
k
=
x
k
⊕
a
i
k
a^k_j=x^k⊕a^k_i
ajk=xk⊕aik
Upper Form Middle
a
i
a_i
ai and
a
j
a_j
aj is the two distinct subscript elements in the original array, K represents the whole of the 31-bit binary number from left to right to K. From the above formula, we can see that K increases continuously from 1 to 31 bits to judge if x is 1, and put the first k bits of all elements in the array into the hash table in the current situation, assuming that during the review process
a
j
k
=
x
k
⊕
a
i
k
a^k_j=x^k⊕a^k_i
ajk =x k_aik satisfies the condition, proving that the k-bit of X can be 1, otherwise it is 1. The program consists of a 31-bit loop (constantly looking for the number of digits in x), with every possible loop
a
j
k
a^k_j
ajk is saved in a hash table, and then we fetch it
a
i
k
a^k_i
aik and
x
k
x^k
xk does XOR. If this result is found in the hash table, it is possible. The current bit of x not found in the hash table cannot be 1. Be aware
a
i
k
a^k_i
aik also traverses so-called
a
j
k
a^k_j
The value of ajk, which is essentially an individual's concept of the whole, all
a
i
k
a^k_i
aik Individuals Compose Storage
a
j
k
a^k_j
ajk's hash table is all! Here are two ways of writing, the second is Official Writing , he operates by moving right, moving all the numbers to the range counted from right to left. Not very well understood, the first method is directly on the original array to get a better understanding from the previous net ~~
class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
if (nums.size() < 2) return 0;
int maxNum = 0;
int flag = 0;
//The key to this question is that the ultimate maximum XOR result must be the number (i.e. the largest number) of all numbers with the highest position being the first 1.
for (int i = 31; i >= 0; --i)
{//Start with maxNum Max to min </span>
set<int> hash;
flag |= (1 << i); //Use flag to take out the first n-i bit of each x, n is 31
for (int x : nums)
{
hash.insert(flag & x); //Each of the first n-i bits removed is stored i n the set for subsequent comparison.
}
int tmp = maxNum | (1 << i); //maxNum is the largest number i n the first n-i bit from the last comparison. Using the tmp attempt, is it possible if the next next nearest one is 1?
for (int x : hash)
{
//X1^tmp=x2 is used here, x1^x2=tmp. Cause: x1^tmp=x2, if both sides are X1 or X1, then tmp=x1^x2.
if (hash.find(x ^ tmp) != hash.end()) //If it exists, it means that the first n-i bit of one number is exclusive to the first n-i bit of another number, or the result is the maxNum
{
maxNum = tmp;
break;
}
}
}
return maxNum;
}
};
class Solution {
private:
// The highest binary bit number is 30
static constexpr int HIGH_BIT = 30;
public:
int findMaximumXOR(vector<int>& nums) {
int x = 0;
for (int k = HIGH_BIT; k >= 0; --k) {
unordered_set<int> seen;
// Put all pre^k(a_j) in the hash table
for (int num: nums) {
// If you only want to keep the part from the top to the k-th binary bit
// Just move it to the right k bit
seen.insert(num >> k);
}
// Currently x contains the parts from the top to k+1 binary bits
// We'll put the k-th binary position of X at 1, which is x = x*2+1
int x_next = x * 2 + 1;
bool found = false;
// Enumeration i
for (int num: nums) {
if (seen.count(x_next ^ (num >> k))) {
found = true;
break;
}
}
if (found) {
x = x_next;
}
else {
// If no a_satisfying equation is found I and a_j, then the k-th binary bit of x can only be 0
// That is x = x*2
x = x_next - 1;
}
}
return x;
}
};