问：使用按位 AND > k ~ 计算数组对可能比 O(N^2) 更好吗？

Question

给定一个数组nums

计数没有。成对（两个元素），其中 按位 AND 大于 K

蛮力

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

更好的版本：预处理以删除所有元素 ≤k 然后暴力

但我想知道，这里的复杂性极限是什么？

我们可以使用 trie、hashmap 方法（如二和）做得更好吗？

（我在Leetcode上没有发现这个问题，所以我想在这里问一下）

Answer 1

让size_of_input_array = N。设输入数组为 B 位数

这是一个易于理解和实施的解决方案。

消除所有 <= k 的值。
上图显示了5个10位数。

第 1 步：邻接图

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

第 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)

Space 复杂度

Overall space complexity = O(BN)

Answer 2

首先，修剪所有内容 <= k。还要对值列表进行排序。

从最高有效位到最低有效位，我们将跟踪我们正在使用的一组数字（最初是所有 ,s=0, e=n）。

令 p 为当前集合中第一个包含 1 的位置。

如果 k 中的位是 0，那么所有能产生 1 世界的东西肯定是好的，我们需要调查那些得到 0 的东西。我们在当前范围内有 (end - p) * (end-p-1) /2 对，并且 (end-p) * <total 1s in this position larger or equal to end> 与以前好的数字更大的组合，我们可以将其添加到解决方案中。为了继续，我们更新 end = p。我们要计算上面所有数字中的 1，因为我们之前只是成对地计算它们，而不是集合中这么低的数字。

如果k中的位是1，那么我们还不能计算任何胜利，但是我们需要消除p以下的所有内容，所以我们更新start = p。

你可以在完成所有操作后停止或 start==end。

详情：

由于在每一步我们都消除了所有具有 0 或所有具有 1 的内容，因此开始和结束之间的所有内容都将具有相同的位前缀。由于值已排序，我们可以进行二进制搜索以查找 p.
对于<total 1s in this position larger than p>。我们已经对值进行了排序。因此，我们可以计算部分和，并为排序列表中的每个位置存储其上方所有数字的每个位位置中 1 的数量。

复杂度：

我们逐位得到 L（数字的位长度），我们进行二进制搜索 (logN)，然后查找和更新 O(1)，所以这是 O(L logN)。
我们必须对 O(NlogN) 进行排序。
我们必须计算部分按位和 O(L*N)。

总计 O(L logN + NlogN + L*N)。

因为 N>>L，L logN 被 NlogN 归入。由于 L>>logN（可能是因为你有 32 位数字，但你没有 40 亿），那么 NlogN 被 L*N 归入。所以复杂度是 O(L * N)。由于我们还需要保留部分和，内存复杂度也是 O(L * N)。

问：使用按位 AND > k ~ 计算数组对可能比 O(N^2) 更好吗？

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

algorithm

bit-manipulation

time-complexity

data-structures