Số xảy ra một lần duy nhất trong mảng

Question

thể trùng lặp:
Finding a single number in a list

Với một loạt các con số, ngoại trừ một số tất cả những người khác, xảy ra hai lần. Thuật toán để tìm số đó chỉ xảy ra một lần trong mảng là gì?

Ví dụ

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

nên trả lại 4

Answer 1

Hãy để số đó xảy ra một lần duy nhất trong mảng được x

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

Kể từ a^a = 0 và a^0 = a

số đó xảy ra ở những cặp hủy bỏ ra và kết quả được lưu trữ trong x

đang làm việc trong 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. Tạo mới int i = 0
2. XOR từng hạng mục với i
3. Sau khi tất cả lặp sẽ được dự kiến ​​số trong i

.210

Answer 3

Vâng tôi chỉ biết lực lượng algo Brute và nó là để đi qua toàn bộ mảng và kiểm tra

Mã sẽ như thế nào (trong C#):

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

Answer 4

Bạn có thể sắp xếp các mảng và sau đó tìm phần tử đầu tiên điều đó không không có cặp. Điều đó đòi hỏi một số vòng lặp để sắp xếp và một vòng lặp cho việc tìm kiếm phần tử đơn lẻ.

Nhưng phương pháp đơn giản hơn là đặt các khóa kép thành 0 hoặc giá trị không thể ở định dạng hiện tại. Cũng phụ thuộc vào ngôn ngữ lập trình, vì bạn không thể thay đổi các loại khóa trong C++ không giống C#. câu trả lời

Answer 5

zerkms' trong C++

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

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

Answer 6

Nếu bạn có số lượng mà không thể được XORed hợp lý (Big Số nguyên hoặc số đại diện như Strings, ví dụ), một cách tiếp cận thay thế mà cũng là O (n) thời gian, (nhưng O (n) không gian thay vì O (1) không gian) sẽ chỉ đơn giản là sử dụng một bảng băm. Thuật toán trông giống như:

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 

Tôi sẽ làm, mã C hoặc C++, nhưng cả hai đều không có bảng băm được tích hợp. (Đừng hỏi tại sao C++ không có bảng băm trong STL, nhưng không có bản đồ băm dựa trên cây đỏ đen, bởi vì tôi không biết họ đang nghĩ gì.) Và, thật không may, tôi không có trình biên dịch C# để kiểm tra lỗi cú pháp, vì vậy tôi sẽ cung cấp cho bạn Mã Java. Nó khá giống nhau, mặc dù.

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