arrays - 快速查找是否有 2 个或更多相等的数字

Question

我有一个经常变化的 N 个不同数字的数组。每次更改后，都有可能两个或更多数字变得相等，我不希望这样。数字 N 可以与最大可能整数一样大。知道更改经常发生，我不想在每次更改后将每个数字与其余数字进行比较。

如何快速找到数组中是否至少有 2 个相等的数字？

Answer 1

这实际上取决于您有哪些其他限制，例如：

1. 你需要保持号码进来的顺序吗？
2. 数字只是被添加了，还是也被删除了？
3. 什么是更常见的操作：添加/删除或检查欺骗？
4. 您需要保留什么 - 集合（即唯一数字）或多重集合（具有多重性的数字）？

有两个基本选项：二叉搜索树和哈希表。

前者会给你O(log(n))平均操作，后者 - O(1); 实际结果将取决于您拥有什么样的流（数字是随机的吗？增加？遵循一个奇怪的非显而易见的模式？）

如果您决定选择 BST，请记住您必须保持平衡。

示例（未经测试）

(defparameter *my-data-array* (make-array 100000))
;; fill *my-data-array*
(defparameter *my-data-table*
  (let ((ht (make-hash-table)))
    (loop for v across *my-data-array*
        do (incf (gethash v *my-data-table* 0)))
    ht))
(defun modify-data-array (pos new-value)
  (let* ((old-value (aref *my-data-array* pos))
         (old-count (decf (gethash old-value *my-data-table*)))
         (new-count (incf (gethash new-value *my-data-table* 0))))
    (setf (aref *my-data-array* pos) new-value)
    (case old-count
      (0 ; old-value is now not in the array
       ...)
      (1 ; old-value is now unique
       ...)
      (t ; old-value is still not unique
       ...))
     (case new-count
      (1 ; new-value was not in the array before
       ...)
      (2 ; new-value was unique before, but not anymore
       ...)
      (t ; new-value was not unique
       ...))))

Answer 2

作为变体，您可以使用Bloom filter。它允许测试是否已经添加了给定的数字。但可能存在误报错误。另一方面，布隆过滤器既节省空间又快速，并且允许您保留数组。如果您很少使用重复数字，布隆过滤器算法将对您很有用，否则您必须经常在线性时间内重新测试数字。