最小XOR值:给定一个由N个整数组成的整数数组A，请在数组中找到具有最小XOR值的一对整数 [英] Minimum XOR value : Given an integer array A of N integers, find the pair of integers in the array which have minimum XOR value

问题描述

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

Given an integer array A of N integers, find the pair of integers in the array which have minimum XOR value Here is the Brute Force solution where we find every pair possible and compute XOR and find the minimum of every pair :

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)复杂度的代码:

Here is the code with O(n*logn) complexity :

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;
}

我的疑问是，排序对查找最小异或值对有何帮助?在此解决方案中，我们仅找到连续排序元素的异或.我们是否会错过其他不连续的潜在最小异或值对?我仍在学习位操作，因此，如果这个疑问看起来太愚蠢，请原谅我.

My doubt is, how does sorting help in finding the minimum xor valued pairs ? In this solution we are finding the xor of only the consecutive sorted elements. Will we not be missing out other potential minimum xor value pairs that are not consecutive ? I'm still learning bit manipulations, so forgive me if this doubt seems too stupid.

推荐答案

XOR在数字之间的绝对差异上是单调的.(如果数字相同，则XOR为零).如果您忽略负数的可能性并以二进制形式写数字，则很明显.

XOR is monotonic in the absolute difference between numbers. (If the numbers are identical, then the XOR is zero). If you ignore the possibility of negative numbers and write the numbers in binary, it becomes obvious.

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

So the minimum value in a sorted list will always be between a particular adjacent pair. And finding that pair is an O(N) traversal.

这篇关于最小XOR值:给定一个由N个整数组成的整数数组A，请在数组中找到具有最小XOR值的一对整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！