java - 哈希集中的项目数量如何影响性能？

Question

我正在寻找在未排序数组中找到最长连续整数序列的解决方案。解决方案是 2 遍方法，其中在第一个方法中，所有元素都添加到哈希集中，在第二遍中，我们检查哈希集中右侧和左侧有多少元素。它看起来像这样:

temp = n;
while(map.get(temp+1) != null) {
    count++;
    map.remove(temp++);
}

其中n是数组中的当前元素。在这种情况下，为什么我们在检查后要从哈希集中删除该元素？解决方案说，如果我们不删除它，时间复杂度将变为 O(mn) 而不是 O(n)。我认为哈希集查找与内容无关？

Answer 1

与HashSet无关，与算法有关。如果您不从集合中删除相邻数字，则会将它们重新处理为下一个序列的第一个元素。