Najlepszy sposób na znalezienie pojedynczej liczby w parach lub trójek

Question

Jest to jedno pytanie z serii pytań. Modyfikuję to, aby nie było duplikowane od innych. Dzięki za całą pomoc.

Pary: Mam tablicę liczb całkowitych. W tablicy każdy element pojawia się dwa razy, z wyjątkiem jednego. Chcę znaleźć ten jeden numer.

Przykład: [2, 4, 2, 1, 4, 1, 3], pojedynczy numer to 3.

Myślałem, że używam HashMap, który zabiera O(n) czasu i O(n) miejsca. Czy są jakieś lepsze rozwiązania? Dzięki.

Trójki: każdy element pojawia się trzy razy, z wyjątkiem jednego. Znajdź ten jeden.

Przykład: [1, 2, 4, 2, 4, 1, 2, 4, 1, 3], pojedynczy numer to 3.

Answer 1

Zastanów się go rozwiązać w sposób „bit”, który odbywa O(n) czas i O(1) miejsca:

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

No tak, mam również rozwiązanie dla znalezienia ani jednego w trójek.

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

Może to być trudniejsze do zrozumienia. Przeczytaj kilka materiałów na temat manipulacji bitami, a następnie sprawdź, jak działa to rozwiązanie.