查找按位数为0的数组中的所有数字对

Question

我最近遇到了一个问题，它是关于计算数组中所有位数为&为0的数字对。所需的复杂度为O（n）或O（nlog（n））或更少。数字范围为1到1000000.

我的方法是写每个数字的二进制形式，然后为每个数字的位检查是否是0或1，如果位是1我可以拿这些数字有0在相同的位置，如果位是0我可以取任何数字作为0 *（任意数字）= 0。但是我的时间复杂度是O（n^2），它不会通过。

Answer 1

我会从给定的数组构建一棵二进制树，这样每个位都会定义我们在树中是向左还是向右。用于3位数字101这将是：

节点 - >（1）右键 - >（0）左 - >（1）右键

（我不知道这里怎么格式化一个二进制尝试，它删除所有多个空间，所以我很抱歉这样可怜的插图）

所以这将需要O（n）（建立分支和创建新节点是O（1））。

然后，使用将带从所述阵列的一个数（X），处理其比特和走在树的递归方法，以使得对于每个位k：

IF (k == num_of_bits) 
    Then print pair (X, current node value) 
     Return 

IF (left branch exists) 
    Then take left branch with X[num_of_bits..k+1] // we go left anyway 
//ELSE - 'else' here was a mistake 
IF X[k] == 0 // if the bit is 0 we can go in both directions 
    Then IF (right branch exists) 
      Then take right branch with X[num_of_bits..k+1] 

现在复杂的计算是有点棘手，因为最坏的情况似乎是所有的比特都是0，但是在树中，你将只有一个分支... 它在我看来，复杂性是O（n * log（n）） - 如果我没有忽略任何东西。

所以总也为O（n）+ O（N *的log（n））=> O（N *的log（n））

Answer 2

您可以使用尝试的概念来解决这个问题。

插入特里：首先，插入特里树中的所有数字。这棵树将是一个二叉树，如果你想有二进制表示001插入1，我们将采取左子为0，右孩子为1，将如下：

根 - >离开（0） - > left（0） - > right（1）

如果路径已经存在，请勿再次添加新节点。在这种情况下，只能遍历树并在路径不存在的地方添加0 0或1。每个叶子节点也将保持每个数字的计数。因此，插入的时间复杂度为O（n * log2（max）），因为我们插入了n个元素，每个插入的时间等于数组最大数量中的位数。

查询请求：对于数组中的每个数字，比较数字n中的位值和您所做树上的位数。从数字的第一位开始。

如果该位是零，横越到右侧或左侧树的，并且如果该位为1， 横移到树的左侧。

对数字的每一位都做这个操作，直到你到达第n位。如果你不能收回第n位，不可能返回。如果达到第n位，则返回存储在叶节点中的计数。 富勒更详细的解释，请参考下面这个链接，

Trie tree

Answer 3

可以是本机暴力破解

import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.Scanner; 

class BitAnd { 

public static void main(String[] args) throws IOException { 
    BufferedReader br= new BufferedReader(new InputStreamReader(System.in)); 
// Scanner sc= new Scanner(System.in);    
    int t=Integer.parseInt(br.readLine()); 
    while(t-->0){ 
     int n=Integer.parseInt(br.readLine()); 
     int arr[]= new int[n]; 

     String s[]=br.readLine().split(" "); 
     for (int i = 0; i < s.length; i++) { 
      arr[i]=Integer.parseInt(s[i]);    
     } 
     int c=0;    
     for (int i = 0; i < arr.length; i++) { 
      for (int j = i+1; j < arr.length; j++) { 
       if((arr[i]&arr[j])==0)c++;     
      }    
     } 
     System.out.println(c*2);    
    }  
    } 
}