c - 在除一个数字外没有重复的数组中找到重复的数字

Question

假设有一个元素数组，除了 1 个数字之外没有重复的元素，

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

如何高效地查找重复号码？我们可以使用哈希表 (HT) 在 O(n) 时间和 O(n) 空间内完成，如下所示。

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

在空间和时间复杂度上是否有更好的方法？

注意:这个问题不是以下两个不同问题的重复。

如果整数是连续的，可以使用此链接中的解决方案how-to-find-a-duplicate-element-in-an-array-of-shuffled-consecutive-integers

如果 n 个元素的数组包含从 0 到 n-1 的元素，则只有此链接有解决方案 Finding duplicates in O(n) time and O(1) space

Answer 1

我不认为你能比 O(n) 时间复杂度做得更好——在最坏的情况下你将不得不接触数据集的每个元素来找到重复项

改善空间消耗的一种方法(以需要一些位旋转以及两次遍历数据集为代价)是使用 Bloom Filter .这个想法是首先遍历数据集:如果你发现一个可能的重复项，那么你将它从数据集中删除并将它添加到哈希表中(如果布隆过滤器正常运行，那么只有大约 1% 的元素会被标记尽可能重复)。然后对过滤后的数据集进行第二次传递，根据可能重复的小哈希表测试元素。

我的代码将使用 Java，因为它是我最熟悉的语言。

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

哈希表的替代方法是使用 Radix Sort ，一种线性时间排序算法。基数排序将具有更好的最坏情况性能(基数排序的 O(n) 与哈希表的 O(n^2) 相比，在您遇到荒谬数量的冲突的不太可能发生的情况下)但平均情况下的性能更差(哈希表实现通常会在仅扫描一半数据集后找到重复项，而基数排序将始终需要多次遍历数据集)。如果您对存储桶使用节省空间的数据结构，例如，基数排序在空间消耗方面也会稍微更有效率。分块列表。

您可以并行化哈希表实现，而不会产生太多的同步开销。使用 t 个线程，每个线程将处理数据集的 n/t 个元素(例如，如果数据集中有 32 个元素和 2 个线程，则线程 0 处理元素 0-15 thread1 处理元素 16-31)，将每个元素放入索引为 absoluteValue(x modulo t) 的桶中。在此之后，每个线程将负责处理具有给定桶索引的所有元素，例如thread0 将处理索引为 0 的所有桶。我正在使用 BlockingQueue用于同步——这允许线程调用队列上的take()，导致线程移除队列的第一个元素或者阻塞直到元素可用；所有其他数据结构都是线程本地的。您需要初始化 dupFinders 变量，以便 DupFinder 实例出现在每个 DupFinder 的 dupFinders 变量的相同索引中(例如，thread0 始终出现在第 0 个索引中，从而确保其 BlockingQueue 中的所有元素都具有 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
  }
}