c++ - 最小异或值 : Given an integer array A of N integers, 找出数组中具有最小异或值的整数对

Question

给定一个由 N 个整数组成的整数数组 A，找到数组中具有最小 XOR 值的整数对
这是蛮力解决方案，我们找到每对可能并计算异或并找到每对的最小值:

int minXOR(int arr[], int n) 
{ 
    int min_xor = INT_MAX; // Initialize result 

    // Generate all pair of given array 
    for (int i = 0; i < n; i++) 
        for (int j = i + 1; j < n; j++) 

            // update minimum xor value if required 
            min_xor = min(min_xor, arr[i] ^ arr[j]); 

    return min_xor; 
} 

这是复杂度为 O(n*logn) 的代码:

int Solution::findMinXor(vector<int> &A) {
    sort(A.begin(),A.end());
    int min=INT_MAX;
    int val;
    for(int i=0;i<A.size();i++)
    {
        val=A[i]^A[i+1];
        if(val<min)
            min=val;
    }
    return min;
}

我的疑问是，排序如何帮助找到最小异或值对？在这个解决方案中，我们只找到连续排序元素的异或。我们不会错过其他不连续的潜在最小异或值对吗？我还在学习一些操作，所以如果这个怀疑看起来太愚蠢了，请原谅我。

Answer 1

XOR 在数字之间的绝对差异方面是单调的。 (如果数字相同，则 XOR 为零)。如果你忽略负数的可能性，把数字写成二进制，就很明显了。

因此，排序列表中的最小值将始终位于特定的相邻对之间。找到那对是 O(N) 遍历。