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

Question

给定一个数组nums

\n

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

\n

暴力破解

\n

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

\n

更好的版本：\n预处理以删除所有元素\xe2\x89\xa4k\n然后暴力破解

\n

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

\n

我们可以使用二和之类的 trie、hashmap 方法做得更好吗？

\n

（我在leetcode上没有找到这个问题所以想到这里问）

\n

Answer 1

让 size_of_input_array = N。令输入数组为B- 位数字

\n

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

\n

\n

\n

• 消除所有 <= k 的值。

  \n
\n

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

  \n
\n

\n

第 1 步：邻接图

\n

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

\n

第 2 步：挑战是避免再次计算相同的对。

\n

为了解决这个挑战，我们借助并查找数据结构，如下面的代码所示。

\n

//unordered_map<int, vector<int>> adjacency_graph;\n//adjacency_graph has been filled up in step 1\n\nvector<int> parent;\nfor(int i = 0; i < input_array.size(); i++)\n    parent.push_back(i);\n\nint result = 0;\nfor(int i = 0; i < adjacency_graph.size(); i++){ // loop 1\n    auto v = adjacency_graph[i];\n    if(v.size() > 1){\n        int different_parents = 1;\n        for (int j = 1; j < v.size(); j++) { // loop 2\n            int x = find(parent, v[j]);\n            int y = find(parent, v[j - 1]);\n            if (x != y) {\n                different_parents++;\n                union(parent, x, y);\n            }\n        }\n        result += (different_parents * (different_parents - 1)) / 2;\n    }\n}\nreturn result;\n

\n

上面的代码中，find和union来自并查数据结构。

\n

时间复杂度：

\n

步骤1：

\n

Build Adjacency Graph: O(BN)\n

\n

第2步：

\n

Loop 1: O(B)\nLoop 2: O(N * Inverse of Ackermann\xe2\x80\x99s function which is an extremely slow-growing function) \n

\n

总体时间复杂度

\n

= O(BN)\n

\n

空间复杂度

\n

Overall space complexity = O(BN)\n

\n