Tek bir sayı çiftleri veya üçlü olarak bulmak için en iyi yol

Question

Bu bir dizi sorudaki bir sorudur. Bunu diğerlerinden çoğaltmak için değiştiriyorum. Yardımın için teşekkürler.

Çiftleri: Bir dizi tam sayı var. Dizide, her öğe bir hariç olmak üzere iki kez görüntülenir. Tek numarayı bulmak istiyorum.

Örnek: [2, 4, 2, 1, 4, 1, 3], tek bir sayı 3.

Benim düşüncem O(n) zaman alır ve O(n) alan bir HashMap kullanmaktır. Daha iyi çözümler var mı? Teşekkürler.

Üçlü: her öğe bir tanesi dışında üç kez görüntülenir. Tek olanı bul.

Örnek: [1, 2, 4, 2, 4, 1, 2, 4, 1, 3], tek bir sayı 3.

Answer 1

O(n) zaman ve O(1) alan alır "bit" Bu arada, bunu çözme düşünün:

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

Peki, evet, ben de üçüzlerde tek tek bulmak için bir çözüm var.

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

Bunu anlamak sizin için daha zor olabilir. Lütfen bit manipülasyonu ile ilgili bazı materyalleri okuyun ve sonra bu çözümün nasıl çalıştığını anlayın.