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作为temp数组的index，检查是否为true即if ( temp[current_value] == true)
4. 如果它是 true，则您已找到重复元素 else set temp[current_value] = true

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