tìm số trùng lặp trong một mảng mà không có bản sao ngoại trừ một số

Question

Giả sử có một loạt các yếu tố mà không có bản sao trừ 1 số,

ex. 1,2,13,4,7,11,2,6 

Làm thế nào để tìm số trùng lặp trong một hiệu quả cách thức? chúng ta có thể làm điều đó bằng cách sử dụng một bảng băm (HT) trong O (n) thời gian và với O (n) không gian như dưới đây.

if(HT.Contains(item)) -> this is the duplicate 
else 
ht.add(item) 

Có cách nào tốt hơn cả về không gian và thời gian phức tạp?

Lưu ý: vấn đề này không trùng lặp với hai vấn đề dưới đây khác nhau.

Nếu số nguyên là liên tiếp các giải pháp trong liên kết này có thể được sử dụng how-to-find-a-duplicate-element-in-an-array-of-shuffled-consecutive-integers

Nếu mảng n phần tử chứa các yếu tố từ 0 đến n-1 chỉ liên kết này có giải pháp Finding duplicates in O(n) time and O(1) space

Answer 1

Các thao tác trên bit đơn mất thời gian (giống như: lấy từ, nhận/đặt 1 bit, đặt từ), so sánh với các hoạt động từ (get/set word).

Nếu bạn biết rằng MIN_VALUE> = 0, cũng biết MAX_VALUE và nó đủ nhỏ, bạn có thể làm một cái gì đó như Jongware đề xuất - bảng băm, nhưng không phải trên bit: giá trị băm chỉ đơn giản là giá trị đó.

#include <stdio.h> 
#include <string.h> 

#define MAX_VALUE 13 +1 // +1 so we don't have do -1 in for loop 

main() 
{ 
    int i; 
    int array[] = { 1,2,13,4,7,11,2,6 }; 
    int array_size = sizeof(array)/sizeof(array[0]); 

    short flags[MAX_VALUE] = { 0 }; 
    for (i = 0; i < array_size; ++i) { 
      if (++flags[ array[i] ] != 1) { 
       printf ("duplicated %d on %d\th position", array[i], i); 
      } 
    } 
} 

Và nó cũng không yêu cầu băm tính toán cho từng phần tử.

Answer 2

Tôi không nghĩ rằng bạn có thể làm tốt hơn so với O (n) thời gian phức tạp - trong trường hợp xấu nhất bạn sẽ phải chạm vào mọi phần tử của tập dữ liệu để tìm ra trùng lặp

Một cách để cải thiện tiêu thụ không gian (với chi phí yêu cầu một số bit twiddling cũng như hai đi qua các tập dữ liệu) là sử dụng một Bloom Filter. Ý tưởng là thực hiện lần đầu tiên vượt qua tập dữ liệu: nếu bạn tìm thấy một bản sao có thể thì bạn xóa nó khỏi tập dữ liệu và thêm nó vào bảng băm (nếu chức năng lọc hoa nở chính xác thì chỉ khoảng 1% các phần tử sẽ được gắn cờ khi có thể trùng lặp). Sau đó, thực hiện lần thứ hai vượt qua tập dữ liệu được lọc, kiểm tra các phần tử dựa vào bảng băm nhỏ của các bản sao có thể có.

Mã của tôi sẽ bằng Java vì đó là ngôn ngữ tôi quen thuộc nhất.

Class DupFinder { 
    BloomFilter filter = new BloomFilter(); 
    HashTable hashTable = new HashTable(); 
    int start = 0; 

    int run(int[] dataset) { 
    // first pass 
    for(int i = 0; i < dataset.length; i++) { 
     if(filter.contains(dataset[i]) { 
     // check if element is in hashTable, else add it 
     if(hashTable.contains(dataset[i]) { 
      return dataset[i]; // duplicate found 
     } else { 
      hashTable.add(dataset[i]); 
     } 

     // remove element from dataset 
     int temp = dataset[start]; 
     dataset[start] = dataset[i]; 
     dataset[i] = temp; 
     start++; 
     } else filter.add(dataset[i]); 
    } 

    // second pass 
    for(int i = start; i < dataset.length; i++) { 
     if(hashTable.contains(dataset[i]) { 
     return dataset[i]; // duplicate found 
     } 
    } 
    return NULL; // no duplicate found 
    } 
} 

Một thay thế cho bảng băm của bạn là sử dụng một Radix Sort, một thời gian tuyến tính thuật toán sắp xếp. Phân loại Radix sẽ có hiệu suất trường hợp xấu nhất tốt hơn (O (n) cho sắp xếp radix, so với O (n^2) cho bảng băm trong trường hợp không chắc bạn chạy vào một số va chạm vô lý) nhưng hiệu suất trung bình tệ hơn (Việc thực hiện bảng băm thường sẽ tìm thấy bản sao sau khi quét chỉ một nửa số liệu, trong khi phân loại radix sẽ luôn yêu cầu nhiều lần vượt qua tập dữ liệu). Phân loại Radix cũng sẽ hiệu quả hơn về mức tiêu thụ không gian nếu bạn sử dụng cấu trúc dữ liệu không gian hiệu quả cho các nhóm, ví dụ: một danh sách chunked.

Bạn có thể song song việc triển khai bảng băm mà không phải chịu quá nhiều chi phí đồng bộ hóa. Sử dụng các chủ đề t, mỗi luồng sẽ xử lý n/t phần tử của tập dữ liệu (ví dụ:nếu bạn có 32 phần tử trong tập dữ liệu và 2 luồng, thì thread0 xử lý các phần tử 0-15 và thread1 xử lý các phần tử 16-31), đặt mỗi phần tử vào một thùng với chỉ mục absoluteValue (x modulo t). Theo đó, mỗi luồng sẽ chịu trách nhiệm xử lý tất cả các phần tử với chỉ mục nhóm đã cho, ví dụ: thread0 sẽ xử lý tất cả các nhóm với chỉ số 0. Tôi đang sử dụng BlockingQueue để đồng bộ hóa - điều này cho phép một chuỗi gọi mất() trên hàng đợi, khiến cho chuỗi xóa phần tử đầu tiên của hàng đợi hoặc chặn khác cho đến khi phần tử trở nên có sẵn; tất cả các cấu trúc dữ liệu khác là thread-local. Bạn sẽ cần khởi tạo biến dupFinders để một cá thể DupFinder xuất hiện trong cùng một chỉ mục của biến dupFinders của DupFinder (ví dụ thread0 luôn xuất hiện trong chỉ mục 0, do đó đảm bảo rằng tất cả các phần tử trong BlockingQueue của nó có absoluteValue (x modulo t) == 0).

Class DupFinder implements Callable<Integer> { 
    private Class Chunk { 
    int size = 0; 
    int chunk = new int[64]; 

    boolean add(int x) { 
     if(size < 64) { 
     chunk[size] = x; 
     size++; 
     return true; 
     } else return false; 
    } 
    } 

    int t = ??? // number of threads 
    private BlockingQueue<Stack<Chunk>> queue = new LinkedBlockingQueue() 
    private DupFinder[] dupFinders = new DupFinder[t]; 
    private Stack<Chunk>[] stacks = new Stack<Chunk>[t]; 

    void add(Stack<Chunk> stack) { 
    queue.add(stack); 
    } 

    // the thread only receives n/t elements of the dataset 
    int call(int[] partialDataset) { 
    // partition dataset elements by their modulus(t) 
    for(int i = 0; i < partialDataset.length; i++) { 
     tempStack = stacks[Math.absoluteValue(partialDataset[i] modulo t)]; 
     if(!tempStack.peek().add(partialDataset[i])) { 
     Chunk chunk = new Chunk(); 
     chunk.add(partialDataset[i]); 
     tempStack.push(chunk); 
     } 
    } 

    // distribute chunk stacks to the appropriate threads 
    for(int i = 0; i < t; i++) { 
     dupFinders[i].add(stacks[i]); 
    } 

    HashTable hashTable = new HashTable(); 
    for(int i = 0; i < t; i++) { 
     // wait for a chunk stack to become available 
     Stack<Chunk> tempStack = queue.take(); 
     while(!tempStack.isEmpty) { 
     tempChunk = tempStack.pop(); 
     for(int i = 0; i < tempChunk.size; i++) { 
      if(hashTable.contains(tempChunk.chunk[i]) { 
      return tempChunk.chunk[i]; // duplicate found 
      } else { 
      hashTable.add(tempChunk.chunk[i]); 
      } 
     } 
     } 
    } 
    return NULL; // no duplicate found 
    } 
}