algorithm - 数组中元素重复的时间复杂度

Question

给定一个包含 n 个随机数的数组，找到一个 O(n*ln n) 算法来检查它是否包含仅使用数组（没有其他复杂数据结构）的某个数字的重复出现。

当您获取每个元素并与其余元素进行比较以检查匹配时，我得到了明显的 O(N*N)。您还可以对其进行排序并比较 n*log n 中的相邻元素。我正在寻找除此之外的东西。

Answer 1

好的，让我来看看这个。

1. 找到数组中的最大元素（比如max）。（O(N) 次操作）
2. 创建一个大小为 的boolean数组（比如temp）max。
3. 遍历原始数组并使用current_value作为index数组temp并检查是否为trueieif (temp[current_value] == true)
4. 如果是true你已经找到了重复元素，否则设置temp[current_value] = true

显然这个算法不是空间有效的，因为我们不知道数组的大小是多少，temp并且临时数组中的大部分空间永远不会被访问，但它的时间复杂度是 O(N)

Answer 2

最好用哈希表替换数组。然后，无需查找最小值/最大值，只需开始将您的数字作为 kyes 放入哈希表中，在每次“放置”之前检查该键是否已经存在。请注意，数组方法无法处理大范围内的数字，例如 min=-2^63，max=2^63，即使它们只有几个。另一方面，哈希表可以轻松处理它们。

但是，我刚刚注意到您只想使用数组。然后您可以使用数组模拟哈希表。有关详细信息，请参见此处：http ://algs4.cs.princeton.edu/34hash/ 您可以选择简单的哈希函数并以简单的方式处理冲突，例如将冲突值放入下一个可用的数组槽中。