快速查找是否有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
       ...))))