algorithm - Q : Count array pairs with bitwise AND > k ~ better than O(N^2) possible?

Question

给定一个数组 nums 计数 不。对(两个元素)其中 按位与 大于 K蛮力

for i in range(0,n):
   for j in range(i+1,n):
       if a[i]&a[j] > k:
           res += 1

更好的版本:
预处理以删除所有元素 ≤k然后蛮力
但我想知道，这里复杂性的限制是什么？
我们可以用像二和的特里哈希图方法做得更好吗？
(我在 Leetcode 上没有发现这个问题，所以我想在这里问)

Answer 1

让 size_of_input_array = N .让输入数组为 B -位数
这是一个易于理解和实现的解决方案。

消除所有值 <= k。

上图显示了 5 个 10 位数字。

第 1 步:邻接图

存储设置位列表。在我们的示例中，为输入数组中索引 0、1、2、3 处的数字设置了第 7 位。

第 2 步:挑战在于避免再次计算相同的对。
为了解决这个挑战，我们借助 union-find 数据结构，如下面的代码所示。

//unordered_map<int, vector<int>> adjacency_graph;
//adjacency_graph has been filled up in step 1

vector<int> parent;
for(int i = 0; i < input_array.size(); i++)
    parent.push_back(i);

int result = 0;
for(int i = 0; i < adjacency_graph.size(); i++){ // loop 1
    auto v = adjacency_graph[i];
    if(v.size() > 1){
        int different_parents = 1;
        for (int j = 1; j < v.size(); j++) { // loop 2
            int x = find(parent, v[j]);
            int y = find(parent, v[j - 1]);
            if (x != y) {
                different_parents++;
                union(parent, x, y);
            }
        }
        result += (different_parents * (different_parents - 1)) / 2;
    }
}
return result;

在上面的代码中， find和 union来自 union-find 数据结构。
时间复杂度:
第1步:

Build Adjacency Graph: O(BN)

第2步:

Loop 1: O(B)
Loop 2: O(N * Inverse of Ackermann’s function which is an extremely slow-growing function) 

总时间复杂度

= O(BN)

空间复杂度

Overall space complexity = O(BN)