algorithm - 求两个值为 2 的整数之间的 Xor 值

Question

给定一个由 N 个整数组成的数组。能查到号码吗 (a[i],a[j]) 对使得 1 <= i < j< = N 并且按位 Xor 值恰好为 2，时间复杂度小于 O(n^2) 或者是否有任何数学公式找到像 a[i] ^ a[j] == 2 这样的对数。

约束

1≤N≤10^5

1≤Ai≤10^6

Answer 1

此问题的有效解决方案可以是 O(n) 时间复杂度。这个想法是基于这样一个事实，即 arr[i] ^ arr[j] 等于 2 当且仅当 arr[i] ^ 2 等于 arr[j]。

1) Initialize result as 0.
2) Create an empty hash set "s".
3) Do following for each element arr[i] in arr[]
   (a)    If 2 ^ arr[i] is in "s", then increment result by 1.
   (b)    Insert arr[i] into the hash set "s".
3) return result.

这是 C++ 实现:

int xorPairCount(vector<int>& arr) {
    int n= (int)arr.size();
    int result = 0;

    unordered_set<int> s;

    for (int i = 0; i < n ; i++) {
        // If there exist an element in set s
        // with XOR equals to 2^arr[i], that means
        // there exist an element such that the
        // XOR of element with arr[i] is equal to
        // 2, then increment count.
        if (s.find(2^arr[i]) != s.end())
            result++;

        // Make element visited
        s.insert(arr[i]);
    }

    return result;
}

请注意，对于此解决方案，我假设数组中没有重复项。如果允许重复，那么解决方案会有点不同。让我知道。

更新

如果数组中有重复项，使用hashmap而不是hashset来统计每个数字出现的频率，因为每次出现都会有一个计数。以下是上述代码的更新:

int xorPairCount(vector<int>& arr) {
    int n= (int)arr.size();
    int result = 0;

    unordered_map<int, int> m;

    for (int i = 0; i < n ; i++) {
        int curr_xor =  2^arr[i];
        if (m.find(curr_xor) != m.end())
            result += m[curr_xor];

        m[arr[i]]++;
    }

    return result;
}