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

Question

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

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

Answer 1

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

1. 您需要维护号码的顺序吗？
2. 这些数字是只添加过，还是也删除了？
3. 什么是更常见的操作:添加/删除或检查重复项？
4. 您需要保留什么 - 集合(即唯一数字)或多重集(数字及其重数)？

有两个基本选项:a Binary Search Tree和一个 Hash Table .

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

如果您决定使用 BST，请记住您必须 keep it balanced .

示例(未经测试)

(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
       ...))))