numero che si verifica solo una volta nella matrice

Question

Eventuali duplicati:
Finding a single number in a list

Dato un array di numeri, ad eccezione di uno numero tutti gli altri, si verificano due volte. Quale dovrebbe essere l'algoritmo per trovare quel numero che si verifica una sola volta nell'array ?

Esempio

a[1..n] = [1,2,3,4,3,1,2] 

dovrebbe restituire 4

Answer 1

Sia il numero che si verifica solo una volta nella matrice sia x

x <- a[1] 
for i <- 2 to n 
    x <- x^a[i] 
return x 

Da a^a = 0 e a^0 = a

numeri che si verificano nella coppia annullano e il risultato viene memorizzato in x

codice di lavoro in C++

#include <iostream> 

template<typename T, size_t N> 
size_t size(T(&a)[N]) 
{ 
    return N; 
} 
int main() 
{ 
    int a [] = {1,2,3,4,3,1,2}; 
    int x = a[0]; 
    for (size_t i = 1; i< size(a) ; ++i) 
    { 
     x = x^a[i]; 
    } 
    std::cout << x; 
} 

Answer 2

1. Crea nuovo int i = 0
2. XOR ogni elemento con i
3. Dopo tutte le iterazioni ci sarà previsto numero in i

Answer 3

Pozzo So solo della forza algo bruta ed è per attraversare tutta una serie e verificare

codice sarà come (in C#):

k=0; 
for(int i=0 ; i < array.Length ; i++) 
{ 
    k ^= array[i]; 
} 
return k; 

Answer 4

Si poteva ordinare l'array e poi trovare il primo elemento che doesn ne ho una coppia Ciò richiederebbe diversi loop per l'ordinamento e un ciclo per trovare il singolo elemento.

Ma un metodo più semplice sarebbe impostare i tasti doppi su zero o un valore che non è possibile nel formato corrente. Dipende anche dal linguaggio di programmazione, in quanto non è possibile modificare i tipi di chiave in C++ a differenza di C#. risposta

Answer 5

zerkms' in C++

int a[] = { 1,2,3,4,3,1,2 }; 

int i = std::accumulate(a, a + 7, 0, std::bit_xor<int>()); 

Answer 6

Se si dispone di quantitativi che non possono essere ragionevolmente XORed (Grandi numeri interi o numeri rappresentati come stringhe, per esempio), un approccio alternativo che è anche O (n), (ma O (n) spazio piuttosto che O (1) spazio) sarebbe semplicemente utilizzare una tabella hash. L'algoritmo si presenta come:

Create a hash table of the same size as the list 
For every item in the list: 
    If item is a key in hash table 
     then remove item from hash table 
     else add item to hash table with nominal value 
At the end, there should be exactly one item in the hash table 

che avrei fatto il codice, C o C++, ma nessuno dei due ha tabelle hash costruito nel (non chiedetemi perché C++ non ha una tabella hash nel STL,. ma ha una mappa hash basata su un albero rosso-nero, perché non ho idea di cosa stessero pensando.) E, sfortunatamente, non ho a disposizione un compilatore C# per testare gli errori di sintassi, quindi ti sto dando Codice Java È piuttosto simile, però.

import java.util.Hashtable; 
import java.util.List; 

class FindUnique { 
    public static <T> T findUnique(List<T> list) { 
     Hashtable<T,Character> ht = new Hashtable<T,Character>(list.size()); 
     for (T item : list) { 
      if (ht.containsKey(item)) { 
       ht.remove(item); 
      } else { 
       ht.put(item,'x'); 
      } 
     } 
     return ht.keys().nextElement(); 
    } 
}