首页 文章

在数组中找到重复的数字,除了一个数字之外没有重复的数字

提问于
浏览 550
5

假设有一个元素数组没有重复,除了1个数字,

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

如何以有效的方式找到重复的数字?我们可以在O(n)时间使用哈希表(HT)并使用如下的O(n)空间 .

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

在空间和时间复杂性方面有更好的方法吗?

注意: this problem is not a duplicate of below two problems 是不同的 .

如果整数是连续的,则可以使用此链接中的解决方案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

2 回答

  • 2

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

    改善空间消耗的一种方法是(使用数据集需要一些麻烦以及两次传递)是使用Bloom Filter . 我们的想法是对数据集进行第一次传递:如果找到可能重复的数据,则将其从数据集中删除并将其添加到哈希表中(如果bloom过滤器正常运行,则只会标记约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)相比,在不太可能的情况下,您遇到了可疑的数量的冲突)但是平均情况性能更差(哈希表实现通常会在扫描一半数据集后找到副本,而基数排序总是需要多次遍历数据集) . 如果您使用节省空间的数据结构,Radix Sort在空间消耗方面也会略微提高效率,例如:一个分块列表 .

    您可以并行化哈希表实现,而不会产生太多的同步开销 . 使用t个线程,每个线程将处理数据集的n / t个元素(例如,如果数据集中有32个元素,2个线程,则thread0处理元素0-15,thread1处理元素16-31),将每个元素放入带索引的桶 absoluteValue(x modulo t) . 在此之后,每个线程将负责处理具有给定桶索引的所有元素,例如, thread0将处理索引为0的所有桶 . 我使用BlockingQueue进行同步 - 这允许线程在队列上调用 take() ,导致线程删除队列的第一个元素或者阻塞直到元素可用;所有其他数据结构都是线程本地的 . 你'll need to initialize the dupFinders variable so that a DupFinder instance appears in the same index of every 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
      }
    }
    
  • 0

    单个位的操作非常耗时(例如:获取字,获取/设置1位,设置字),与字操作(获取/设置字)进行比较 .

    如果您知道MIN_VALUE> = 0,那么也知道MAX_VALUE并且它足够小,您可以执行Jongware建议的操作 - 哈希表,但不能使用位:哈希值只是那些值 .

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

    并且它也不需要为每个元素计算哈希值 .

相关问题