Количество, которое происходит только один раз в массиве

Question

Можно создать дубликат:
Finding a single number in a list

Дан массив чисел, для одного числа всех остальных, за исключением, происходят дважды. Какой алгоритм должен найти этот номер, который встречается только один раз в массиве ?

Пример

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

должен вернуть 4

Answer 1

Пусть число, которое происходит только один раз в массиве будет x

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

С a^a = 0 и a^0 = a

Числа, которые происходят в паре сокращаются, и результат сохраняется в x

Рабочий код в С ++

#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. Создать новую int i = 0
2. XOR каждый элемент с i
3. После всех итераций будет ожидать число в i

Answer 3

Well я знаю только грубой силы алгоритмом и он должен пройти через весь массив и проверить

код будет как (в C#):

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

Answer 4

Вы можете отсортировать массив, а затем найти первый элемент, который Безразлично У меня есть пара. Для этого потребуется несколько циклов для сортировки и цикл для нахождения одного элемента.

Но более простым методом было бы установить двойные ключи в ноль или значение, которое невозможно в текущем формате. Также зависит от языка программирования, так как вы не можете изменять типы ключей в C++, в отличие от C#. Ответ

Answer 5

zerkms' в C++

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

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

Answer 6

Если у вас есть запасы, которые не могут быть разумно операции XOR (Big Целые или номера представлены в виде строк, например), альтернативный подход, который также является O (п), (но O (n) пространство, а не O (1) пространство) было бы просто использовать хеш-таблицу. Алгоритм выглядит следующим образом:

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 

Я хотел бы сделать код, C или C++, но ни один из них хэш-таблицы встроенный (Не спрашивайте меня, почему C++ не имеет хэш-таблицу в STL,. но имеет хэш-карту, основанную на красно-черном дереве, потому что я понятия не имею, о чем они думают.) И, к сожалению, у меня нет компилятора C# для проверки синтаксических ошибок, поэтому я даю вам Java-код. Однако это очень похоже.

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