查找按位數爲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);    
    }  
    } 
}