Der beste Weg, um die einzelne Zahl in Paaren oder Tripeln zu finden

Question

Da dies eine Frage in einer Reihe von Fragen ist. Ich modifiziere das, um es nicht von anderen zu duplizieren. Danke für die Hilfe.

Paare: Ich habe eine Reihe von ganzen Zahlen. Im Array erscheint jedes Element zweimal mit Ausnahme eines Elements. Ich möchte diese einzelne Nummer finden.

Beispiel: [2, 4, 2, 1, 4, 1, 3], einzelne Nummer ist 3.

Mein Gedanke ist es, eine HashMap, die O(n) Zeit und O(n) Platz zu verwenden. Gibt es bessere Lösungen? Vielen Dank.

Dreifache: Jedes Element erscheint dreimal außer einem. Finde das einzige.

Beispiel: [1, 2, 4, 2, 4, 1, 2, 4, 1, 3], einzelne Nummer ist 3.

Answer 1

Überlegen Sie es in der „Bit“ Art und Weise zu lösen, die O(n) Zeit und O(1) Platz in Anspruch nimmt:

public class Solution { 
    public int singleNumber(int[] A) { 
     if (A.length==0) return 0; 
     if (A.length==1) return A[0]; 

     int result = A[0]; 

     for (int i=1; i<A.length; i++) { 
      result = result^A[i]; 
     } 

     return result;   
    } 
} 

Nun ja, ich habe auch die Lösung, die die einzelnen in Tripel für die Suche.

public class Solution { 
    public int singleNumber(int[] A) { 
     int result = 0; 

     for (int i = 0; i < 32; i++) { 
      int curr = 0; 
      for (int num : A) { 
       curr += (num >> i) & 1; 
      } 
      result += (curr % 3) << i; 
     } 

     return result; 
    } 
} 

Dies kann für Sie schwieriger zu verstehen sein. Bitte lesen Sie einige Materialien über Bit-Manipulation und dann herausfinden, wie diese Lösung funktioniert.