c++ - 查找从未排序的数组中删除的一个和 N 个元素

Question

我正在尝试针对以下问题实现有效的解决方案，“假设在一个从 1 到 n 的未排序数组中，如何查找是否删除了一个数字，如果删除了 n 个数字怎么办？”

让我说一下，我在编码方面没有问题，如果有人可以贡献我的基本想法，我就在这里。我想，将所有元素存储在一个哈希表中，索引是数字本身(即 hash(1)=1)，然后从 1 到 n 检查哈希表是否存在该值。这将花费 O(n) 时间。如果删除了多个数字，我当然会建议这样做。对于单个值，我会计算从 1 到 n 的 nums 的总和，然后减去数组的总和。

然而，对于删除的 n 个数字，我可以添加任何内容以提高效率。 (如果涉及负数，虽然我的解决方案是像 (O(12)=12=-12) 那样存储，但基本链接会自动将时间复杂度增加到 O(2n)。这个问题实际上是我问这个问题的原因，但对于唯一积极因素的任何想法也可能有所帮助。)

Answer 1

你的解决方案是最好的，你不能有比 O(N) 更好的复杂度(O(2N) 实际上是 O(N))如果你有一个很好的函数，如果你有负数并不重要映射你的值(value)。对于数字，我会建议一个小于 n 并且是质数的数字，让我们称这个数字为 P。f(x) = x%P(对于值 x，键为 x%P)对于 P = 9913 我们应该有:hash[10] = 10, 9923,-9903 和所有具有(它们的值)%P 的数字等于数组中的 10。 您可以使用链表或 vector 来摆脱碰撞。对于数字 Y，您应该将 Y 存储在索引 Y%P 处，并且对于 i in range(1..n) 进行一次遍历，您应该查看位于 i%P 位置的哈希表，因为 i( 基本上是 O(1 ) 查询的复杂性) 就是这样。希望它有所帮助。对不起我的英语:(