查找范围内的缺失元素

让我们通过一个例子来理解这个问题。问题的输入将是一个数组和两个整数，low 和 high。我们需要找出 low 和 high 之间缺失的元素。

让我们举一个例子：

如果数组是 [2,4,6,8,10]，并且 low=5，high=10。

数组中 low 和 high 之间，即 5 和 10 之间缺失的值是 6,7,9。

所以答案是 6,7,9。

所以现在我们需要实现一个代码来打印不在给定 low 和 high 值之间的值。

代码

输出

说明

首先，我们现在需要输入向量的大小和输入元素，并将它们存储在一个向量中。

上面的代码行将获取向量大小的输入，获取向量元素作为输入，并将它们存储在一个名为 vec 的向量中。

接下来，我们需要提示用户输入 low 和 high 值，即我们需要在哪个范围中查找缺失的数字。

上面的代码行将处理获取 l 和 h 值输入的情况；我们需要一个 ans 向量来存储给定范围内的缺失值。

如何找到缺失值，

由于用户给出了 low 和 high 值的输入，我们需要使用循环从 l 迭代到 h。然后，对于 l 和 h 之间的每个元素，我们需要搜索该元素是否存在于向量中，并且为了检查向量，在最坏的情况下，我们需要遍历整个数组。

因此，我们可以轻松地使用两个 for 循环找出 l 和 h 之间缺失的元素。

使用上面的代码行，如果向量中存在缺失元素，它们将被添加到 ans 向量中，否则不会被添加。

如果没有添加任何元素，则表示给定范围的向量中没有缺失元素。

否则，我们需要打印这些缺失值。

由于我们已将缺失值存储在 ans 向量中，现在我们需要打印它们。

上面的代码行将打印给定范围内的缺失数字。

让我们讨论时间和空间复杂度

时间复杂度： 如果我们忽略输入所花费的时间，

我们从 l 遍历到 h，对于 l 和 h 之间的每个元素，我们都在大小为 n 的向量中搜索该元素，因此总共花费的时间是

(h-l+1)*n。

然后，如果缺少任何值，我们需要打印它们，在最坏的情况下，打印它们所花费的时间是 (h-l+1)。

因此，总共花费的时间是 n*(h-l+1) + (h-l+1)，我们将其视为 n*(h-l+1)。

空间复杂度

我们已经为存储缺失值分配了空间，在最坏的情况下，所需空间将是 (h-l+1)

时间复杂度： n*(h-l+1)

空间复杂度： (h-l+1)

在上述方法中，不需要额外的空间；我们可以直接打印缺失值而无需将它们存储在向量中。

在上面的代码中，我们可以直接打印它们而不是将它们存储在向量中，即，将元素推入向量中。

在此代码中，如果没有打印任何元素，我们需要假设没有缺失元素。

让我们部署代码

代码

输出

说明

与之前的代码没有变化。我们只是将空间复杂度降低到 O(1)。

但是时间复杂度保持不变。

但是我们也需要降低时间复杂度，所以让我们实现降低时间复杂度的代码

代码

输出

在上面的输出中，打印了 5 到 10 之间不在输入数组中的缺失元素。

这里，1 到 5 之间的所有值都在给定数组中，所以没有打印任何元素。

说明

首先，我们需要输入向量的大小和向量元素，同时在获取元素作为输入时，我们还需要将值插入到映射中。

这是从用户获取大小输入和向量元素的代码，我们还创建了一个名为 mp 的映射，它将存储向量元素的值。

现在，我们需要输入范围值，然后我们需要打印给定范围内给定向量中缺失的值。

我们如何找到？

我们知道在映射中搜索需要恒定的时间；我们需要一个循环来从 l 迭代到 h，即范围，并搜索每个元素是否在映射中存在；如果元素不在映射中，那么我们可以说该元素在给定范围内缺失。

上述代码部分将获取范围的输入，并打印给定范围内向量中不存在的所有值。

让我们讨论时间和空间复杂度

时间复杂度： 如果我们忽略输入所花费的时间，我们从 l 遍历到 h，对于每次迭代，我们在映射中搜索元素，这需要时间为 (h-l+1)*log(N)，其中 n 是映射的大小。

时间复杂度： (h-l+1)*log(n)

空间复杂度

这里，我们使用了空间来将值存储到映射中，因此在最坏的情况下，映射大小可以是 n，即所需空间为 O(N)

空间复杂度： O(n)

我们仍然可以优化上述代码；在这里，搜索元素需要 log(n) 时间。使用无序集可以将时间从 log(n) 减少到 O(1)。

所以，让我们使用无序集实现代码。

代码

输出

解释

与之前的代码没有变化。我们只是用无序集代替了映射。

让我们讨论时间和空间复杂度

时间复杂度： 在最坏的情况下，从 l 遍历到 h，h-l 可以是 n，因此代码的时间复杂度为 O(N)（这里，在集合中搜索需要 O(1) 时间）

空间复杂度： 我们使用无序系列，因此消耗的空间存储其向量元素。

因此，空间复杂度为 O(N)。

先前方法的简要解释