Il modo migliore per trovare il numero singolo in coppia o in tripla

Question

Poiché questa è una domanda in una serie di domande. Sto modificando questo per renderlo non duplicato da altri. Grazie per tutto l'aiuto.

Coppie: Ho una matrice di numeri interi. Nell'array, ogni elemento appare due volte tranne uno. Voglio trovare quel numero singolo.

Esempio: [2, 4, 2, 1, 4, 1, 3], il numero singolo è 3.

Il mio pensiero è quello di utilizzare un HashMap, che richiede lo spazio O(n) e lo spazio O(n). Ci sono soluzioni migliori? Grazie.

Tripli: ogni elemento appare tre volte tranne uno. Trova quello singolo.

Esempio: [1, 2, 4, 2, 4, 1, 2, 4, 1, 3], il numero singolo è 3.

Answer 1

Pensa di risolvere nel modo "bit", che prende O(n) tempo e lo spazio O(1):

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;   
    } 
} 

Beh, sì, ho anche la soluzione per trovare il singolo in triple.

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; 
    } 
} 

Questo può essere più difficile da comprendere. Si prega di leggere alcuni materiali sulla manipolazione dei bit e quindi capire come funziona questa soluzione.